Programmers: 큰 수 만들기

문제

• https://programmers.co.kr/learn/courses/30/lessons/42883
• 분류: 그리디!

문제 설명

• 특정 수에서 K개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기

핵심[주의]

• Permutation을 생각할 수 있음!
  • 그러나, 숫자가 1924일 때,
  • 14는 가능할 지언정, 41은 불가능함
  • 즉 만들어지는 수 순서는 항상 주어진 수 그대로 유지해야됨
• 이 문제는 그리디
  • 처음에 그냥 Permutation 구할까 하다가 위 조건때문에 안함
  • 주어진 수 그대로 라는 조건에서 추가적으로 다른 조건이 생김

number = "1231234"
length = 7
K = 3
만들어야되는 숫자 = 4[Length - 3]

이 경우, 맨 뒤 3자리의 "234"는 고를 수 없음
-> 234 중 하나를 고르면, 숫자 4개를 만들 수 없음
-> 주어진 수 그대로 수열을 유지해야되기 때문에 "234" 중 2를 선택하면 234 라는 답이 나오지만, 만들어야 되는 숫자가 4이므로 모순[불가능]

알고리즘

• number = 인풋 숫자[String], k = 제거할 수의 갯수, answer = 답[String]
• target 변수 초기화
  • number.length() - k
  • 요 변수는 answer에 넣어야 되는 문자들의 갯수를 의미
• tmp -> target - 1
  • number의 뒤에서부터 target-1만큼은 선택할 수 없습니다.[핵심 참고]
• 선택할 수 있는 부분[범위]에서 가장 큰 수 & 인덱스 찾기
• 해당 수를 answer에 집어넣고, 찾은 인덱스 앞에 있는 스트링 모두 제거
  • 순열 유지
  • 1231234에서 3이 큰 수이고, 인덱스가 2인 경우[0부터 시작]
  • 제거한 스트링은 1234가 됨
• 계속 반복

Before Code

맨 처음 짠 코드, 인덱스와 큰 수 모두 손으로 구한 격

#include <string>
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int target = number.length() - k;
    while (number.length() > 1) {
        int tmp = target - 1; // target - 1 choice not possible
        int limit = number.length() - tmp;
        int maximum_index = INT_MIN;
        char maximum_number = CHAR_MIN;
        for (int i = 0; i < limit; i++) {
            if (maximum_number < number[i]) {
                maximum_number = number[i];
                maximum_index = i;
            }
        }

        answer += maximum_number;
        number = number.substr(maximum_index+1, number.length());
        target--;
    }

    if (target != 0) {
        answer += number;
    }
    return answer;
}

After Code

이 편한 max_element.. 코드 양이 팍 줄었습니다...

#include <string>
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int target = number.length() - k;
    while (number.length() > 1) {
        int tmp = target - 1; // target - 1 choice not possible
        int limit = number.length() - tmp;
        auto iter = max_element(number.begin(), number.begin()+limit);

        answer += *iter;
        number.erase(number.begin(), iter+1);
        target--;
    }

    if (target != 0) {
        answer += number;
    }
    return answer;
}