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

1. 문제

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스 (programmers.co.kr)

 

2. 풀이 1

간단하게 생각해서

 

각 숫자를 뒤에서부터 인덱스를 전부 기록했다.

 

그 다음 가장 큰것 중 완성 시킬 수 있는 것을 앞쪽부터 선택해나가면

 

답이 완성된다.

 
 
string selectNum(string& number, string& answer, int last, int k, vector<vector<int> >& idx) {
    if(k == 0)
        return answer;
 
    for(int i = 9; i > -1; i--)
    {
        while(idx[i].size() != 0 && idx[i].back() < last)
            idx[i].pop_back();
        if(idx[i].size() == 0 || number.size() - idx[i].back() < k) 
            continue;
        else {
            answer += to_string(i);
            last = idx[i].back();
            idx[i].pop_back();
            return selectNum(number, answer, last, k - 1, idx);
        }
    }
    return "-1";
}
 
string solution(string number, int k) {
    string answer = "";
    vector<vector<int> > idx(10, vector<int>());
 
    for(int i = number.size() -1; i > -1; i--)
            idx[(int)number[i] - '0'].push_back(i);
 
    return selectNum(number, answer, 0, number.size() - k, idx);
}

 

3. 풀이 2

max_element 의 iter을 받아서  erase (begin() + i, iter); 을 실행하여

조건문으로 스킵을 안해도 바로 건너 뛰게 할 수 있다.

 

덤으로 select 대신 number.begin() + i + 1 + k 를 사용하고

erase한 만큼 k를 감소시키면서 nuber에서 직접적으로 답을 구할 수 있다.

 

이 풀이는 위 풀이보다 직관적이다.

 

해당 구간안에서 가장 큰것을 선택하고 그 큰 것 뒤는 전부 지우는 것이다.

 

iterator로 number을 처음부터 탐색했으면 더 구현이 직관적이었을 것이다.

 

 

 
 
string solution(string number, int k) {
    vector<char> answer;
    int maxc = '0', select = number.size() - k;
    number = "0" + number;
    
    for(int i = 0; i < number.size(); i++) {
        if(select == 0) 
            break;
        if(number[i] < maxc) 
            continue;
        int last = number.size() + 1 - select;
        maxc = *max_element(number.begin() + i + 1, number.begin() + last);
        answer.push_back((char)maxc);
        select--;
    }
    return string(answer.begin(), answer.end());
}

 

3. 풀이3 

이 풀이는 다른 답안의 첫번째 풀이이다.

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