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

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

풀이

처음에 이 문제를 보자마자 백트레킹 방법이 떠올랐다. 하지만 그리디 알고리즘을 활용한 풀이를 공부하면서 내가 기존에 문제를 너무 좁은 시야를 가지고 푼 것 같다고 생각했다. 그래서 이번 문제 풀이를 이해하는데 조금 어려웠다. 자유롭고 말랑말랑한 생각을 할 수 있도록 다양한 방법들을 연습해야겠다.

number string의 앞 자리에서부터 하나씩 골라서 담으면서, 지금 담으려는 number[i] 보다 작은 것들은 빼줬다!

※ s.back() < number[i] 정수로 변환하지 않고 비교해도 괜찮을까?
-> 가능하다! C++에서 char의 대소비교는 사전에 나타나는 순서를 따르는데 한 글자짜리 문자를 비교할때는 괜찮다!

※ 그리디 알고리즘
-> 현재 단계에서 최적해라고 생각되는 접근 방법을 선택해서, 뒤에 어떤 선택을 하든간에 내가 지금 단계에서 선택한 것이 결국에 최적해를 보장할 것이다!
-> 결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 방식의 알고리즘

시간 복잡도

• O(n)

코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string s = "";
    for(int i = 0 ; i < number.length() ; i++){
        while(!s.empty() && s.back() < number[i] && k > 0){
            s.pop_back();
            k--;
        }
        if(k == 0){ // 제거할 수 있는 수가 이제 없다면 number의 뒷부분을 s에 더해주고 break
            s += number.substr(i, number.length() - i);
            break;
        }
        s.push_back(number[i]);
    }
    // k가 0에 도달하지 못한 경우에는 뒤에 더 붙어있으므로 substr로 필요한 개수만큼 잘라준다.
    return s.substr(0, number.size() - k);
}