[프로그래머스]큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

 

---

풀이

 

maxIndex =-1;

index를 두개를 사용한다. 

 

"1231234"를 예로 보자. 

k=3이기 때문에 총 7-3=4개의 문자가 출력된다.

 

1.

  1. 2. 3. 1. 2. 3. 4.

 

1,2,3,1 중에서 최대값을 저장하고 그에 해당하는 maxIndex를 저장한다. (3이 최댓값, maxIndex는 2)

1,2,3,1 중에서 1개를 고르는 이유는 뒤의 숫자가 3개가 남아야 하기 때문이다.

 

왜냐하면 여기서 1개를 고르고 , 나머지 3개를 골라야 총 4개를 고를 수 있음.

 

2.

  1. 2. 3. 1. 2. 3. 4.

 

이젠 앞의 1,2,3은 고려할 필요가 없다. 왜냐하면 3이 선택됐기 때문

3의 다음부터 1,2 중에서 최대값을 저장하고 그에 해당하는 maxIndex를 저장한다. (2가 최댓값, maxIndex는 4)

 

이미 정해진 1개에 더해 이 과정에서 1개를 고르고 나머지 2개를 골라야 총 4개를 고를 수 있음.

 

3.

  1. 2. 3. 1. 2. 3. 4.

 

앞의 선택된 1,2,3,1,2는 고려하지 않고 3 중에서 최댓값을 선택한다. (3 선택)

 

4.

  1. 2. 3. 1. 2. 3. 4.

 

나머지 4 중에서 최댓값을 골라준다. (4 선택)

 

 

결론적으로 중요한 것은 maxIndex+1부터 lastIndex까지의 가장 먼저오는 최댓값을 구해준 뒤,

그것을 maxIndex로 바꾸어준다.

lastIndex는 '몇 개의 문자가 더 선택 될지' 에 따라 결정된다.

 

---

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    int needed=number.length()-k;
    int i,j;
    int max=-2147000000;
    int maxIndex=-1;
    int tmpIndex;
    
    int lastIndex=number.length()-needed;
    
    for(int i=needed;i>0;i--)
    {   
        max=-2147000000;
        for(j=maxIndex+1;j<=number.length()-i;j++)
        {

            if(max< number[j])
            {
                max = number[j];
                tmpIndex=j;
            }
        }
        maxIndex=tmpIndex;
        answer += number[maxIndex];
    }
    
    return answer;
}

 

그리디 문제라서 다른 스킬적인건 사용되지 않았다.