프로그래머스/큰 수 만들기(Greedy)/C++

문제 설명

 

다양한 방법으로 풀 수 있는데, 나는 큐를 사용해서 풀었다. 

 

 

 

주의할 점

: 같은 숫자들이 있는 경우에도 반드시 k개의 수를 제거하여 가장 큰 수를 만들어야 한다는 점. 작은 수를 골라서 제거하는 방식으로는 틀리기 쉽다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
처음에 사용한 직접 정의한 최대값 인덱스 찾기 함수
int find_max_index(string &n, int start, int end){
    int max = -1;
    int max_index = 0;
    
    for(int i = start; i<=end; i++){
        if (n[i] == '9') return i;
        
        if (max < n[i]) {
            max = n[i];
            max_index = i;
        }
    }
    
    return max_index;
}
*/

string solution(string number, int k) {
    queue<char> q;
    int index = 0;
    int start = -1;
    int firstk = k;
    string answer = "";
    
    while(k > 0){
        index = max_element(number.begin()+start+1,number.begin()+start+2+k) - number.begin();
        q.push(number[index]); // 구간별 최대값을 구하여 큐에 저장
        k = k - (index - start - 1);
        start = index;
    }
    
    char x;
    int end = 0;
    
    while(answer.size() < (number.size() - firstk)){
        if(!q.empty()){ // 큐에 있는 숫자들을 먼저 꺼냄
            x = q.front();
            answer += x;
            q.pop();
        }
        else{ // 큐가 비었다면 마지막 원소 뒤의 원소들을 그대로 붙여넣음
            for(int i = index+1; i<number.size(); i++){
                answer += number[i];
            }
        }
    }
    
    
    
    return answer;
}

 

 

디버깅 기록

: 양 옆의 두 수보다 모두 작다면 그 수를 지우는 방식으로 시도하였는데, 앞서 말한 주의할 점을 지키지 못해서 실패했다. 그 이후로는 부분적으로 최대값을 구해 그 값들만을 남기는 방식으로 접근하였다. string의 인덱스를 다루는 데 아직 서툴러서 더 간결하게 만들 수 있는 걸 늘이고 늘여서 작성하게 되었다. answer에 붙여넣는 방식이 아닌, number에서 직접 지워가는 방식을 사용할 수도 있었을 것이다. 

 

 

 

피드백

: 문자열과 더 친해지자! 변하는 문자열 인덱스를 자유자재로 활용할 수 있는 능력이 필요해 보인다. 문제를 해결할 방법을 생각할 때도, 반례를 머릿속으로 생각해본 후 그걸 커버할 방법까지 대강 떠올린 후에 구현하는 것도 좋은 방법이다. 처음 시도했던 방법은 머리로만 생각해도 반례가 쉽게 떠오르고, 그걸 컨트롤하느니 차라리 다른 방법을 시도하는 게 낫다고 결론 내리게 될테니까 안 되는 방법에 매달리는 시간을 줄이자. 되는 방법과 안 되는 방법을 구분하는 지혜를 기르자.