프로그래머스. 큰 수(c++) / Greedy

그냥 완탐으로 하기에는,,, 시간제약도 있을 것 같고 애초에 Greedy를 연습하려고 선택한 문제이기에 Greedy로 풀기 위해 노력했다.

하지만,,,아이디어가 도저히 떠오르지 않아 아이디어만 다른 블로그를 참고했다.

 

핵심 아이디어

 

#1924를 예로 들어보겠습니다.

1. k값이 2이므로 4-2 = 2글자가 출력됩니다.

 

2. 그렇다면 앞에서 (0, 1, 2)2까지 검사를해서 큰 수를 찾으면 됩니다.

1924에서 앞에서 2까지인 부분은 192 입니다.

이중에서 가장 큰 숫자는 9가 됩니다.

 

3. 9를 사용했으므로 검사는 9의 뒤부터 탐색하게됩니다.

한 번 뽑았으므로 뒤에 검사하는 부분을 하나 증가시킵니다.

24가 남게되고 이중에서 가장 큰 숫자는 4입니다.

 

4. 따라서 정답은 94가 됩니다.

 

이런식으로 범위를 정해놓고 가장 큰 수를 구하고 이러한 작업을 반복한다.

 

생겼던 문제

아래 코드에서 temp값이 각 범위에서 가장 큰 값을 저장하는 변수인데

이 문제에서는 0~9까지가 가능한 수이기 때문에 temp를 0으로 지정하게 되면, 범위의 최대값이 0일 경우 tempIdx값이 제대로 갱신되지 않아 올바르지 않은 값을 가지게 될 수도 있다.

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    
    int num = number.size()-k;
    int idx = 0;
    for(int i=num; i>=1; i--){
        // 자연수의 범위가 0~9이기 때문에 temp를 0으로 지정하게되면 
        // 최대 값이 0일 경우 tempIdx 값이 제대로 갱신되지 않아 올바르지 않은 값을 가지게 된다.
        int temp = -1;
        int tempIdx = 0;
        for(int j=idx; j<=(number.size()-i); j++){
            if(temp<number[j]-'0'){
                temp = number[j]-'0';
                tempIdx = j;
            }
        }
        idx = tempIdx+1;
        answer += to_string(temp);
    }
    
    return answer;
}

 

참고 블로그

mungto.tistory.com/45