[c++] 프로그래머스 - 큰 수 만들기(Level 2)

문제

코딩테스트 연습 - 큰 수 만들기

 

코드

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

string solution(string number, int k) {
    string answer = "";
    
    int index = 0;
    for(int i=0; i<number.length()-k; i++){
        int max_val = 0;
        for(int j=index; j<=k+i; j++){
            if(number[j]=='9'){ // 10번 테케가 상당히 빨라진다.
                max_val = number[j]-'0';
                index = j+1;
                break;
            }
            if(number[j]-'0'>max_val){
                max_val = number[j]-'0';
                index = j+1;
            }
        }
        answer+=to_string(max_val);
    }
    return answer;
}

 

풀이

문제 이해는 쉬웠는데 저는 상당히 오래 걸렸던 문제였습니다. k개의 수를 제거한다는 말은 결국 (어떤 수 - k개의 수) 자리를 가진 숫자를 만들어 내야 한다는 것을 의미합니다.

• 따라서 처음 for문은 number.length() - k 만큼 돌아줍니다.
• 두 번째 for문의 조건이 상당히 어려운데 int j= index; j<=k+i; j++라고 주게 되면 젤 처음에 0 <k 만큼 돌게 되고 이것은 곧 어떻게든 (number.length() - k) 자릿수의 수를 만든다는 것을 보장하게 됩니다.
• if(number[j]=='9') 문장은 없이 돌려도 통과가 되지만 테스트 케이스 10번의 경우에서 압도적으로 느려집니다.