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

👓 문제 설명

---

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

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

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

입출력 예

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

---

💣 제한 사항

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

---

🚨 접근 방법

가장 큰 수가 되려면 더 큰 값이 높은 자릿수에 위치해야한다. (1과 3인 경우 13x 31o)
그렇다면 문자열의 맨 앞에서부터 하나 뒤에 위치하는 수와 값을 비교해야한다.
만약 n번째 수가 n+1번째 수보다 크다면 n+1번째 수의 값을 지운다.
이렇게 지운 개수 cnt가 k와 같다면 종료한다.

위 방법으로 코드를 제출한 결과 마지막 테스트케이스만 통과를 하지 못했다.
반례를 생각해본 결과
마지막 숫자까지 비교를 하였지만, cnt가 k와 같지 않은 경우이다.
이는 즉 9999911과 같은 경우이다.
따라서 더 지워야하는 개수 k-cnt만큼 마지막 문자열을 잘라주면 해결할 수 있었다.

---

🚈 초기 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
string solution(string number, int k) {
    int cnt=0;
    int idx=0;
    while(cnt!=k){
        if(idx<number.length()-1&&number[idx]<number[idx+1]){
            number.erase(number.begin()+idx);
            cnt++;
            idx=0;
            if(cnt==k)break;
        }
        else{
            idx++;   
        }
    }
    return number;
}

🚈 제출 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
string solution(string number, int k) {
    int cnt=0;
    int idx=0;
    while(cnt!=k){
        if(idx<number.length()-1&&number[idx]<number[idx+1]){
            number.erase(number.begin()+idx);
            cnt++;
            idx=max(0,idx-1);
        }
        else{
            idx++;
        }
        if(idx>number.length()-1){
            number.erase(number.length()-(k-cnt),k-cnt);
            break;
        }
    }
    return number;
}