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

여기를 클릭하면 문제를 볼 수 있습니다.

📕 문제 설명

---

📕 문제 풀이

본인이 푼 방법은 다음과 같습니다.
두 번째 입출력 예인 number = "1231234", k = 3를 사용하여 설명해보겠습니다.
저는 주어진 문자열에서 k개를 제거하는 대신 빈 문자열에 문자 len-k개를 추가하는 방식으로 풀이하였습니다. (len=number.size());

주어진 문자열의 각 문자마다 자릿수에 대한 정보를 추가해줍니다. (이미지 참고)

이제 len-k번째 문자열에 들어갈 숫자를 찾으면 됩니다.
즉, 위의 예에 적용하면 len=7, k=3이니 len-k=4번째 문자에 들어갈 숫자를 찾으면 됩니다. 그러니 자릿수 정보를 활용하면 자릿수가 4보다 작은 2, 3, 4는 추가될 수 없습니다. 그러므로1, 2, 3, 1 중 가장 큰 수를 찾으면 되고 그 수는 3이 되겠습니다.

그리고 답은 아마 3XXX가 되겠지요. 이제 3번째 문자를 찾아줄 건데 그 문자는 이전에 찾은 3보다 뒤에 있는 문자여야 합니다. 그러므로 3 뒤의 문자부터 탐색을 시작합니다. 그러면 조건을 충족하는 문자는 1, 2가 되고 그 중 가장 큰 수는 2입니다.

이와 같은 방식으로 남은 문자들도 찾아주면 됩니다.

이제 이 알고리즘을 코드로 나타내봅시다.

---

📕 Code

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    vector<pair<int,int>> n;	// number와 자릿수 정보를 넣기 위한 변수
    int len = number.size();
    for(int i=0; i<len; i++)
        n.push_back(make_pair(number.at(i)-'0', len-i));	// 자릿수 채워 넣기
        
    int max, max_idx;
    int begin = 0, idx=len-k;	//begin: 이전에 찾은 문자 바로 뒤 index, idx: 몇번째 문자
    while(idx > 0)	//len-k개의 문자를 채울때까지
    {
        max = -1;	// 주어진 문자열에 0이 포함된다는 사실!!
        for(int i=begin; i<len && n[i].second>=idx; i++)	// 이전에 찾은 문자 뒤 index부터 k자릿수 문자까지
        {
            if(max < n[i].first)	// 최대 찾기
            {
                max = n[i].first;
                max_idx = i;
            }
            if(max == 9)	// 최대가 9면 더 이상 찾을 필요 없음
                break;
        }
        answer += (max + '0');	// 최대를 문자열에 추가 (k번째 문자가 됨)
        begin = max_idx+1;	// 다음 탐색의 시작은 이 문자 뒤 index부터!
        idx--;	// 그 다음 문자 찾기
    }
    
    return answer;
}

---

📕 후기

안 풀린다 싶을 땐 잠시 쉬었다 풀자...!