[프로그래머스] 큰 수 만들기
April 20, 2021
https://programmers.co.kr/learn/courses/30/lessons/42748
문제
문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
풀이
그리디하게 앞에서부터 현재 위치 다음에 자기보다 큰 숫자가 나오면 현재 위치에 있는 숫자를 삭제한다. 삭제한 뒤에는 문자열이 새로 배치되었으므로 다시 처음으로 돌아가서 탐색을 다시 해줘야한다.
코드
{% raw %}
#include <string>
#include <vector>
using namespace std;
string solution(string number, int k) {
int eraseCount = 0;
int initialSize = number.size();
while (eraseCount != k) {
for (int i = 0; i < number.size() - 1; i++) {
if (number[i] < number[i + 1]) {
number.erase(number.begin() + i);
break;
}
}
eraseCount++;
}
if (number.size() != initialSize - k) {
number.pop_back();
}
return number;
}
{% endraw %}
