🎯문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
| number | k | return |
|---|---|---|
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
✏️풀이
코드
class Solution {
public String solution(String number, int k) {
// 탐색을 진행할 위치
int index = 0;
StringBuilder answer = new StringBuilder("");
// 만들어야하는 자릿수만큼 반복
for(int i = 0; i < number.length() - k; i++) {
// 최댓값
int max = 0;
// 탐색을 진행할 위치부터 넘어가지 않는 범위까지
for(int j = index; j <= k+i; j++) {
// 최댓값보다 크다면
if(max < number.charAt(j) - '0') {
// 최댓값을 바꿔주고
max = number.charAt(j) - '0';
// 탐색의 시작 위치 변경
index = j+1;
}
}
// 최댓값을 저장
answer.append(max);
}
return answer.toString();
}
}설명
그리디를 사용하여 진행하였다.
우리는 number 중 k개를 제외한 숫자 중 가장 큰 숫자를 반환하려고 한다. 때문에 (number.length() - k)만큼 반복을 진행하였다.
이후 탐색을 진행할 위치부터 범위만큼 반복을 진행하여 해당 구간 중 최댓값을 선정한다. 그리고 그 다음부터 탐색을 진행하도록 index의 위치를 바꿔준다.
예를 들어,
| number | k | return |
|---|---|---|
| "1231234" | 3 | "3234" |
이렇게 구성이 되어있다고 할 때,
두번째 반복문에서 j = index부터 k+i까지 반복을 진행한다.
index는 맨 처음 0으로 초기화를 했으니, 0부터 k+i = 3+0 = 3까지 반복을 진행하는 것이다.
그렇다면 "123" 중 가장 큰 값은 3이 될 것이고, 이때 j는 2이다. 그렇다면 나올 수 있는 가장 큰 값의 맨 첫번째는 3이 되는 것이고, 이후 뒤의 탐색을 통해서 진행을 하면 된다.
다시 한 번 반복을 했을 때, i = 1, j = 2+1 = 3이 될 것이다. 그리고 k+i = 3+1 = 4가 된다.
"12" 중에서 큰 값은 2가 되고 이때 index는 j+1 = 4+1 = 5가 될 것이다.
또 한 번 반복을 진행했을 때, i = 2, j = 5이고 k+i = 3+2 = 5가 된다.
"3" 밖에 없으므로 3, 마지막 반복도 똑같이 진행이 되므로 "4"
지금까지 나온 "3234"가 3개를 제외한 가장 큰 값이 되는 것이다.
StringBuilder에 저장했던 값을 toString()으로 반환하면 문제를 해결할 수 있다!
💡느낀 점
문제를 풀다가 많이 막히게 되는 부분이 시간초과이다. 이번 문제 역시도 처음에 시간초과에 걸렸으나 StringBuilder를 사용하여 해결할 수 있었다. 문제에서 의도한 알고리즘대로 풀지 않아서 시간초과가 난 것인지 아니면 다른 이유인지는 모르겠다.. 하지만 여러 방식을 사용해서 시간 안에 푸는 것 역시도 실력이라고 생각이 들기 때문에 앞으로는 시간을 생각하면서 조금 더 빠른 방식을 고민해봐야할 것 같다.
링크
