[C++] [그리디 알고리즘] [프로그래머스] 큰 수 만들기

      로재의 개발 일기       [

[Level 2] 큰 수 만들기

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

  문제

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

  생각 및 구현

return 되는 결과도 입력과 마찬가지로 순서는 지키기 때문에

( 8941 에서 8은 9보다 먼저 나오기 때문에 98은 불가능하다 )

숫자를 몇개를 버려야 하는지 그리고 몇 개가 뒤에 있어야 하는지

그리고 9인 경우는 해당 for에서 break를 하여 효율성을 높인다.

소스코드

/*
 * https://programmers.co.kr/learn/courses/30/lessons/42883
 */
 
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
string solution(string number, int k) {
    int n = number.size();
    k = n - k;            // k 재정의 사용할 수 있는 수의 갯수
    string ans;            // 정답 string
 
    // Maximum value, least k from last index
    int max_idx = -1;
 
    // flag는 자리수를 의미한다
    // flag 0은 가장 큰 자리 수
    for (int flag = 0; flag < k; flag++) {
        int cur_max = 0;
 
        // max_idx : 직전에 처리한 숫자의 위치
        // i는 직전에 처리한 수보다 뒤에 위치하게 된다.
        // n - k + flag : 1092에서 2개의 숫자를 추출할 경우
        //         : 최대 값인 9는 뒤에 숫자가 최소 하나가 있어야한다
        for (int i = max_idx + 1; i <= n - k + flag; i++) {
            int value = number[i];
            if (cur_max < value) {
                cur_max = value;
                max_idx = i;
 
                // 효율성 문제 해결
                if (value == '9')
                    break;
            }
        }
        // 아스키코드를 숫자로 바꾼다
        ans += to_string(cur_max - '0');
    }
 
    return ans;
}
 
int main() {
    string number;
    int k;
 
    cin >> number >> k;
    cout << solution(number, k);
 
    return 0;
}

마무리

효율성을 고려해야 하는 문제였다.