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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

어떤 숫자의 길이를 size라고 했을 때, 어떤 숫자에서 k개의 숫자를 제거해야한다는 말은 결국 size - k 개의 숫자를 선택하라는 말과 같다. 그리고 앞자리의 숫자가 클수록 큰 숫자이기 때문에 [0, size - k) 범위에서 가장 큰 숫자를 고른다. 한가지 숫자를 선택했다고 가정하자. 그리고 그 숫자의 위치가 i라고 하면, 그 다음에 고를 숫자는 [i+1, i+1 + size - k)이 된다는 것을 알 수 있다. 따라서 계속해서 동일한 방식으로 size-k개의 숫자를 선택하면 된다.

예시를 보면서 이해해보자.
ex) number = 1924, k = 2
이 경우 number.size() - 2로 총 2개의 숫자를 뽑을 수 있다. 앞의 2자리부터 살펴보면 1 9 중에서 9가 더 크므로 9를 선택한다. 그렇게 되면 십의 자리 숫자가 9로 결정된 것이다. 그리고 이번엔 일의 자리를 선택해야하는데 십의 자리로 9를 선택했으므로 그 다음 숫자인 2와 4 중에서 숫자 1개를 선택해야한다. 4가 더 큰 숫자이므로 정답은 94가 된다.

코드를 구현하는 과정에서는 substring 함수를 사용해서 구현하였다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

    // 고른 숫자의 갯수
    int cnt = 0;
    int size = number.length();
    while (cnt < size - k) {
        char max_num = 0;
        int max_idx = 0;
        // size - k - 1 - cnt는 탐색 범위에서 제외된다
        for (int i = 0; i < number.size() - (size - k - cnt - 1); i++) {
            if (max_num < number[i]) {
                max_num = number[i];
                max_idx = i;
            }
        }
        cnt++;
        answer += number[max_idx];
        number = number.substr(max_idx + 1);
    }
    return answer;
}