프로그래머스 lv 2. 42883 큰 수 만들기 c++ **다시 풀어보기**

https://school.programmers.co.kr/learn/courses/30/lessons/42883

#include <bits/stdc++.h>

using namespace std;

string solution(string numbers, int k){
    string answer="";
    stack<char> s;
    
    for(char num: numbers){
        while(!s.empty() && s.top() < num && k>0){
            s.pop();
            k--;
        }
        s.push(num);
    }
    while(k>0){
        s.pop();
        k--;
    }
    while(!s.empty()){
        answer=s.top()+answer;
        s.pop();
    }
    return answer;
}

 

그리디 문제라기 보다는 뭔가 stack의 활용 문제같은 느낌의 풀이이다. 

 

다른 사람의 풀이를 보면, 가장 처음에 나와있는 가장 좋아요가 많은 풀이를 첨부해볼것인데, 

이 풀이의 경우 내가 돌려보니까 훨씬 빠르게 도는것 같다 

#include <bits/stdc++.h>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    answer = number.substr(k); 
    for(int i = k-1;i >=0;i--){
        int j = 0;
        do{
            if(number[i] >= answer[j]){
                swap(number[i],answer[j]);
                j++;
            }
            else break;
        }while(1);
    }
    return answer;
}

 

위의 풀이, 굉장히 헷갈린다. 간결하고 동작도 빠른데 , 확 이해가 가지 않는다. 

아무래도 이 코드의 경우는 시간을 두고 지속적으로 확인하면서 더 분석해보아야 할것 같다. 

 

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    int biggest = 0;
    int idx = 0;

    for (int i = 0; i < number.length(); ++i)
    {
        if (biggest < number[i])
        {
            biggest = number[i];
            idx = i;
        }

        if (i == k)
        {
            i = idx;
            ++k;
            answer.push_back(biggest);
            biggest = 0;
        }
    }

    return answer;
}

추가적으로 위의 코드에 대한 댓글도 이게 정석적이고 모범답안인것 같다 라는 식으로 아주 좋은 평가를 받는 코드인데, 

이 코드또한 같이 분석해보면 좋을것 같다. 

 

처음에는 그냥 이 코드에 대한 해법은 결국 stack 하나인가보다, 이건 stack 문제수준 아닌가 싶었으나, 다른 사람의 풀이를 보니까 정말 풀이가 각양각색이다. 아주 다양한 풀이가 있는 문제이다. 

알고리즘 문제풀이를 할때 너무 갇힌 생각을 하지 않도록 주의하자.