[프로그래머스 Lv.2 / C++] Day66. 큰 수 만들기

2024. 08. 08 - 코딩테스트 스터디 Day66

 
 

01. 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 
 

02. 제한사항

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

 
 

03. 입출력 예

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

 
 

04. 풀이 및 답

오늘도 문제를 풀기 전 그림을 그려 이해해 보았다.
number = 4177252841, k = 4인 경우의 동작에 대해 생각해 보았다.

우선 큰 수를 만들기 위해서는 앞자리 수가 커야 한다.
앞 자리 수를 큰 수로 만들기 위해서 시작 부분부터 k까지의 수 중 가장 큰 수를 구한다.
 
startIndex(0)부터 k + i(4)까지의 영역에서 가장 큰 값을 선택하도록 한다.
 

가장 큰 값인 7을 가장 앞자리에 두고, 다음 동작을 진행한다.
이제 maxIndex로 설정한 2의 다음 인덱스를 startIndex로 둔다.
 
다시 startIndex(3)부터 k + i(5)까지의 영역에서 가장 큰 값을 선택하도록 한다.
 

해당 영역에서 가장 큰 값인 7을 그다음 자리에 두고, 다음 동작을 진행한다.
이제 maxIndex로 설정한 3의 다음 인덱스를 startIndex로 둔다.
 
다시 startIndex(4)부터 k + i(6)까지의 영역에서 가장 큰 값을 선택하도록 한다.
 

해당 영역에서 가장 큰 값인 5를 그 다음 자리에 두고, 다음 동작을 진행한다.
이제 maxIndex로 설정한 5의 다음 인덱스를 startIndex로 둔다.
 
다시 startIndex(6)부터 k + i(7)까지의 영역에서 가장 큰 값을 선택하도록 한다.
 

해당 영역에서 가장 큰 값인 8을 그 다음 자리에 두고, 다음 동작을 진행한다.
이제 maxIndex로 설정한 7의 다음 인덱스를 startIndex로 둔다.
 
다시 startIndex(8)부터 k + i(8)까지의 영역에서 가장 큰 값을 선택하도록 한다.
k만큼 숫자를 제외시켰기 때문에 사실상 이 뒤부터는 그대로 answer에 저장된다.
 
 
코드 전문

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int len = number.size();
    int startIndex = 0;
    
    for (int i = 0; i < len - k; i++) {
        int max = number[startIndex];
        int maxIndex = startIndex;
        
        for (int j = startIndex; j <= k + i; j++) {
            if (number[j] > max) {
                max = number[j];
                maxIndex = j;
            }
        }
    
        answer.push_back(max);
        startIndex = maxIndex + 1;
    }
    
    return answer;
}

startIndex를 0으로 초기화해 두고 시작한다.
 
max에 startIndex가 가리키는 값을, maxIndex에 startIndex 값을 넣는다.
startIndex부터 k + i까지의 값을 비교하면서 해당 영역에서 가장 큰 값을 max에, 그 인덱스를 maxIndex에 저장한다.
이렇게 찾아낸 max값을 answer에 저장하고, startIndex를 maxIndex의 다음 값으로 설정한다.
위 동작을 (number의 길이 - k)만큼 반복한다.
 
이렇게 하면 필요없는 값을 실제로 삭제하지 않고도 원하는 값만을 빼내서 answer에 저장할 수 있다~
 
 

정답!

---

끝
 
 
참고한 게시글

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