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

programmers.co.kr/learn/courses/30/lessons/42883

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

1. index를 활용하여 문제를 풀려면 최종 결과물의 length를 계산해서 code를 짜야하는데 어떻게 할 지 엄두가 나지 않았다.
2. 다른 분이 짠 코드를 보고, 생각난 아이디어를 밀어붙여서 어떻게든 완성시켜야 한다는 걸 알게 되었다.

---

풀이1. Index를 이용한 풀이

    string solution(string number, int k) {
        string answer;
        int begin = 0;
        int cvrted_size = number.size() - k;

        for(int i=0; i<cvrted_size; ++i){
            int idx = begin;
            char max_Num = number[begin];
            for(int j=begin; j<=i+k; ++j){
                if(number[j]>max_Num){
                    idx = j;
                    max_Num = number[j];
                }
            }
            begin = idx+1;
            answer+=max_Num;
        }
        return answer;
    }

---

풀이2. Stack을 이용한 풀이

    string solution(string number, int k) {
        stack<int> stk;
        stk.push(number[0]);
        for(int i=1; i<number.size();++i){
            while(!stk.empty() && stk.size()-1 + number.size()-i >= number.size()-k
                && stk.top() < number[i] ){
                stk.pop();
            } 
            // 아래 조건을 넣지 않아 12테스트 케이스를 통과하지 못 했다.
            // "999", k=2, 답="99"
            if(stk.size()<number.size()-k) stk.push(number[i]);
        }
        string answer;
        while(!stk.empty()){
            answer+=stk.top();
            stk.pop();
        }
        reverse(answer.begin(), answer.end());
        return answer;
    }

while의 조건이 길어져서 지저분하게 나왔다. while 문의 두 번째 조건을 설명하자면 다음과 같다.

스택에서 하나를 뺀 개수 + 남은 숫자 개수 >= 결과로 나올 수의 개수

stk.size()-1 >= i-k 로 정리해서 사용해도 된다.

 

풀이3. 실패한 첫 풀이

    string solution(string number, int k) {
        string max_num = number;
        while(k>0){
            string cur_max =  max_num.substr(0,0)+ max_num.substr(0+1);
            for(int i=1; i<max_num.size(); ++i){
                string cur = max_num.substr(0,i)+ max_num.substr(i+1);
                if(cur_max<cur){ 
                    cur_max = cur;
                }
            }
            max_num = cur_max;
            k--;
        }
        return max_num;
    }

정확성 테스트는 통과했지만 효율성 테스트는 통과하지 못했다.

 

string.erase를 썼다가 원본값이 자꾸 바뀌어 그 다음 for loop를 돌 때 문제가 생겼다. 그래서 substring을 사용했다.