문제 설명
어떤 숫자에서 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" |
나의 풀이
import java.util.*;
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder(number);
for (int i = 0; i < sb.length() - 1; i++) {
while (i >= 0 && k > 0 && sb.charAt(i) < sb.charAt(i + 1) ) {
sb.deleteCharAt(i--);
k--;
}
}
for (int n = 0; n < k; n++) {
sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
}
Java
복사
Remark
•
그리디 알고리즘 문제
•
풀이 아이디어
◦
맨 앞부터 시작해서, 바로 오른쪽에 자기보다 더 큰 수가 있는 수를 삭제하는 것을 반복
◦
하지만 이렇게 하면 시간복잡도가 O(이 되어 10번 테스트 케이스가 시간초과가 나는데, 아래 최적화를 해줘서 통과함
▪
바로 왼쪽보다 더 큰 수 X 가 나타난 경우, X의 바로 왼쪽에 같거나 큰 수가 올 때까지 왼쪽 수를 계속 삭제
▪
예를 들면 입력이 4321115이고 k가 4일 경우
v--5의 바로 왼쪽에 5보다 같거나 큰 수가 올 때까지 k를 소모하며 삭제
4321115 | k = 4
43211 5 | k = 3
4321 5 | k = 2
432 5 | k = 1
43 5 | k = 0
Java
복사
•
스택을 이용한 다른분들 풀이
◦
왼쪽으로 넣는 스택을 상상 → 오른쪽에서 들어오는 수가 왼쪽의 더 작은 수들을 pop 시키며 들어오게 함
◦
스택은 이렇게 쓰는거구나 싶었던 풀이법
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
Java
복사
