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

문제 설명

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

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

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

입출력 예

number ="1924"  k=2    return "94"

number="1231234" k=3 return "3234"

해결 과정

k=2개라는 것은 제가 만들어야 하는 숫자는 number.length()-k라는 겁니다. 그러면 가장 가장 큰 수를 1자리 씩 찾아서 vector에다 집어 넣으면 금방 풀 수 있었습니다.

입출력 예를 예시로 하면 1924에서 제가 만들어야 하는 자리수는 number.length()-2이므로 2개가 됩니다. 그럼 10의 자리수를 만드려면 적어도 1, 9, 2 정도는 비교 해야 합니다.(4를 뽑으면 그다음 숫자를 뽑을 수가 없습니다.) 그 중에서 가장 큰 수인 9를 뽑고 거기에 공백을 집어 넣어버렸습니다. 그 다음에는 1 24 만 남고 여기에서 1의 자리수를 뽑아 내면 가장 큰 수인 4가 뽑혀서 94가 나오게 됩니다.

2번째 예시로 1231234에서 제가 만들어야 하는 자리수는 number.length()-3=4가 됩니다. 1000의 자리수 중에 가장 큰 수를 만드려면 1, 2, 3, 1정도 비교할 수 있습니다. 그 뒤에 234를 비교하면 4자리 수를 만들 수가 없습니다. 그러므로 1,2,3,1 중에 3이 가장 큰 수이고 그 다음 100의 자리수는 비교하면 1, 2," " ,1, 2,  중에 2가 가장 큰 수 가 되겠고 10의 자리수는 1, " ', " ", 1, 2, 3중에 3이 되겠고 1의 자리수는 4가 되면서 3234가 만들어 지게 됩니다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

string solution(string number, int k) {
	string answer = "";
	int need = number.length() - k;
	int cmax = 0;
	int ccount = 0;
	int j;
	vector<int> temp;
	for (int i = need; i>0; i--) {
		cmax = 0;
		ccount = 0;
		for (j = 0; j<number.length() - i+1; j++) {
			if (cmax<number[j]) {
				cmax = number[j];
				ccount = j;
			}
		}
		number.replace(0,ccount+1," ");
		
		temp.push_back(cmax);
	}
	for (int i = 0; i<temp.size(); i++)
		answer += temp[i];
	return answer;
}