[프로그래머스] 큰 수 만들기 (Lv.2)
https://school.programmers.co.kr/learn/courses/30/lessons/42883
문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 한다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있으며, 이 중 가장 큰 숫자는 94이다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어진다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하라.
나의 답안(오답)
내가 생각한 구조는 다음과 같다.
- 가장 큰 수가 되기 위해, 주어진 수의 맨 앞에서 k+1번째까지 숫자 중 가장 큰 수가 가장 앞에 놓여야 한다.
- 가장 앞에 놓일 수가 정해지고 나면, 그 뒤부턴 그 다음 자리의 숫자와 비교하여 더 작을 경우 하나씩 제거한다.
- k개만큼 제거되면 남은 숫자가 답이 된다!
이를 코딩으로 짜보았으나, 테스트케이스는 통과됐으나 오답으로 처리되었다.
다시 확인해보니 예외가 많았다.
다른 풀이법을 찾아보니, 굳이 k+1번째 자리에서 가장 큰 수를 찾을 필요 없이, 맨 앞자리부터 다음 숫자와 비교하여 더 작을 경우, 하나씩 제거해나가면 되는 문제였다..
<오답입니다>
class Solution {
public String solution(String number, int k) {
char[] num_char = number.toCharArray();
char[] answer = new char[number.length()-k];
int count = 0;
answer[0] = num_char[0];
for (int i=1; i<=k; i++) {
if (answer[0] <num_char[i]) {
answer[0] = num_char[i];
count++;
}
}
int j = 1;
for (int i=count+1; i<num_char.length; i++) {
if (count < k) {
if (i != num_char.length-1 && num_char[i] < num_char[i+1]) {
count++;
} else {
answer[j] = num_char[i];
j++;
}
} else {
answer[j] = num_char[i];
j++;
}
}
return String.valueOf(answer);
}
}
모범 답안
- 스택 타입의 변수 생성
- 다음 자리의 수와 비교하며 현재 숫자가 더 작을 경우 stack에서 제거 후 k값 1 감소
- k가 0이 되면 result값을 문자열로 변환하여 반환
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);
}
}
<테스트10 통과 X>
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder(number);
for (int i = 0; i+1 < sb.length() && k>0; i++) {
if(sb.charAt(i) < sb.charAt(i+1)) {
sb.deleteCharAt(i);
i=-1;
k--;
}
}
if(k!=0)
sb.delete(sb.length()-k, sb.length());
return sb.toString();
}
}
그냥 앞에서부터 1개씩 비교해가면 되는 것이었는데 굳이 어렵게 생각하여 풀지 못했다.
stack 타입을 이용하여 숫자를 앞에서부터 비교한다는 점이 포인트이다.
이런건 대체 어떻게 생각해내는 건지 참 신기하다.
나도 언젠간 이렇게 될 수 있겠지..?
복습
1. 문자열 -> 문자배열 : toCharArray()
String str = "abcde"
char[] arr = str.toCharArray();
for (char a: arr ) {
System.out.println(a);
} // 출력: a b c d e
2. 문자배열 > 문자열: String.valueOf(객체) / new String(객체)
String str = "abcde";
char[] arr = str.toCharArray();
String result = new String(arr);
System.out.println(String.valueOf(arr));
System.out.println(result);
// 출력: abcde abcde