프로그래머스 Level 2 큰 수 만들기(Greedy) C++

큰 수 만들기

어떤 숫자에서 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

코드

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
 
    int numSize = number.size() - k;
    int start = 0;
    for(int i=0; i<numSize; i++) {
        char maxNum = number[start];
        int maxIdx = start;
        for(int j=start; j<=k+i; j++) {
            if(maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;
            }
        }
        start = maxIdx + 1;
        answer += maxNum;
    }
 
    return answer;
}

설명

numSize는 처음에 주어진 number의 길이에서 k를 뺀 값이다.

k는 뺄 숫자의 개수이기 때문에 그렇게 되면 numSize는 answer의 길이가 됨

바깥쪽 for문을 numSize만큼 반복한다.

start는 탐색을 시작할 인덱스이다.

위의 예제 중 number="4177252841", k=4일 경우를 가지고 설명해보겠다.

number의 길이가 10이고 뺄 숫자의 개수가 4이다.

* 2020.09.22 댓글 보고 내용 수정

오류가 있었네요. 코드가 버젓이 써있었는데 이런 실수를 하다니 ㅠㅠ

i=0일 때 j는 0부터 4+0=4까지 반복한다.

이렇게 하는 이유는 j[5]~j[9]까지 더 큰 숫자(최적의 답)이 있다고 하더라도 answer의 길이가 6이어야 하므로 고르지 못하기 때문이다.

그러면 선택할 수 있는 숫자는 4, 1, 7, 7, 2 중 하나이고 maxNum에는 7이, maxIdx에는 2가 담기게 된다.

안쪽 for문을 다 돌고 나서 start는 maxIdx +1  = 2+1=3으로, answer의 상태는 "7"이다.

i=1일 때 j는 3부터 4+1=5까지 반복한다.

이때 선택할 수 있는 숫자는 7, 2, 5 중 하나이고

maxNum = 7, maxIdx = 3, start = 4, answer= "77"

i=2일 때 j는 4부터 4+2=6까지 반복한다.

이때 선택할 수 있는 숫자는 2, 5, 2중 하나이고

maxNum = 5, maxIdx = 5, start = 6, answer = "775"

이것을 반복하면 답은 "775841"이 된다.