728x90
문제 설명
어떤 숫자에서 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) {
int count = 0; //제거한 숫자의 개수
int t = 0;
while (count < k && t < number.length()) {
if (number[t] < number[t + 1]) {
number.erase(t, 1); //뒤에 숫자가 더 크면 제거
count++;
t = 0; //다시 0부터 검사
}
else t++;
}
if (count != k) number.erase(number.end() - (k - count)); //모두 검사후 숫자가 순차적으로 감소하면 뒤에서부터 k-count개 제거
return number;
}
greey(탐욕법) 유형의 문제였는데,
솔직히 나는 아직도 dfs/bfs, BS(Binary Search) 같이 알고리즘이 탁탁 눈에 보이는게 아니면
아니면 그냥 뇌피셜로 푸는것 같다.. ㅋ
코드 풀이를 하자면,
문자열을 돌면서 t번째 숫자가 t+1번째 숫자보다 작으면, t번째 문자를 제거해주었다.
이때, while문을 사용했는데, count값이 k가 되거나, t가 문자열의 범위를 벗어났을 때
정지하도록 했다.
만약 while문이 끝나고도, 즉 number의 숫자가 순차적으로 감소하고 있을 때는
뒤에서 k-count개 만큼 제거해주었다!
728x90