라인 코테에서 떨어지고 이런 저런 생각이 많이 들었다. 사고력이나 프로그래밍 스킬이나 해당 문제를 풀어낼 수 없는 정도의 수준은 아니라고 생각이 되는데, 문제 풀이 속도가 너무 느리다는 판단이 들었다. 어떻게 문제 풀이 속도를 늘릴 수 있을까 많은 생각이 들었다.
속상하기도 했지만 처음 취준 시작할 때 생각했듯이 코테는 다른 전형에 비해서 솔직하고, 노력에 비례한다고 생각한다. (아마도?) 내가 노력을 더 해서 더 많은 문제를 풀었다면 풀이를 떠올리는 과정이든, 그것을 코드로 표현해내는 과정에서의 스킬이나 함수 사용이든 그 어떤 부분에서라도 시간이 줄어들었을 것이다. 그렇기에 결국은 내 노력이 부족했다고 생각한다 !
또 다시 새로운 코테들이 다가오고 우선은 더 많은 문제들을 풀어보는 방법뿐이 없지 않을까 생각한다 ! 화이팅 ! 🔥🔥🔥🔥🔥🔥
그래서 오늘 푼 문제는 프로그래머스 고득점 키트 그리디 알고리즘 분류에 있는 level2의 문제이다.
https://programmers.co.kr/learn/courses/30/lessons/42883
문제 설명
어떤 숫자에서 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" |
풀이 방법
큰 수와 관련된 알고리즘 문제는 굉장히 많다. 그러한 문제들을 해결할 때 생각해야 하는 핵심은 오직 하나다 ! 큰 수를 만들기 위해서는 자릿수가 큰, 즉 앞에 있는 숫자들이 커야한다 !
이 문제도 역시 그러한 관점에서 풀이 방법을 고민해 나갔다. 먼저 k개를 모두 제거할 때 까지 반복문을 수행해야 한다. 그러면서 k개를 제거해서 앞에 큰 숫자들이 올 수 있도록 만들어야 한다. 그렇기 때문에 나는 입력 문자열에서 k개 이하를 제거해서 맨 앞에 올 수 있는 범위까지를 탐색하며 가장 큰 수를 찾고, 그 숫자는 최종 결과를 담을 String 변수에 저장하고 그 앞의 숫자들은 제거하였다. 그리고 제거한 개수만큼 k를 감소시켜 주었다. 그리고 number는 삭제하거나 확정한 숫자를 제거한, 즉 탐색하며 찾은 가장 큰 수 뒤의 부분만으로 변경시켜주었다. 이 과정을 반복하고 k개 만큼 제거하여 반복문이 종료되면, 최종적으로 반환되는 값은 확정된 문자열 + 남은 문자열이다.
이렇게만 알고리즘을 작성했을 때, 위에 제공된 테스트 케이스는 모두 만족을 하여 제출을 하였으나, 마지막 테스트 케이스에서 실패가 떴다. 그래서 내가 생각하지 못 한 코너 테스트 케이스를 찾아서 개선을 시도했다. 우선 그 코너 케이스들은 아래와 같다.
코너 케이스
number k return "999" 1 "99" "9991" 2 "99" "1119" 2 "19"
여기서의 문제는 입력 문자열에서 k개 이하를 제거해서 맨 앞에 올 수 있는 범위 내에서 가장 큰 수가 맨 앞인 경우이다. 이 경우에는 해당 loop에서는 제거할 문자가 없어 k가 감소되지 않는다. 그래야 남은 문자열에서 k개를 제거하는 경우까지 계산할 수 있기 때문이다. 하지만 남은 문자열의 길이가 k인 경우, 즉 이제 남은 문자열들을 제거하면 되는 경우에 index out of range exception이 발생하는 것이다.
그래서 만약 남은 문자열의 길이가 k와 같게 된다면, 이미 큰 숫자들부터 앞에 채택한 후이고, 남은 문자열은 모두 제거해야 하는 상황이기 때문에 남은 문자열을 모두 지워주고 반복문을 종료하는 조건 하나를 추가해주었다.
코드
public class Solution {
public static String solution(String number, int k) {
StringBuilder answer = new StringBuilder();
int max, index;
while (k > 0){
if(k >= number.length()){
number = "";
break;
}
max = 0;
index = 0;
for(int i=0; i<=k; i++){
if((number.charAt(i)-'0') > max){
max = number.charAt(i)-'0';
index = i;
}
}
answer.append(number.charAt(index));
number = number.substring(index+1);
k-=index;
}
return answer + number;
}
}개선된 풀이
문제 풀이를 완료한 후 다른 사람의 코드를 살펴보았다. 그러면서 이 문제의 분류가 왜 greedy인지 그리고 더 간단하게 풀이할 수 있는 방법을 알 수 있었다. 이 문제는 단순히 문자열을 순차적으로 탐색하며 현재의 숫자가 앞의 숫자보다 크다면, 앞의 숫자들을 제거하기만 하면 되는 것이었다. 내가 처음 언급했던 큰 수 만들기의 핵심이 전부였던 것이다. 왜 문자를 꼬아 생각했는지 모르겠다. 알고리즘이 직관적이지 않기도 하지만 시간 효율성 측면에서도 number = 1929, k = 2인 경우에 내 알고리즘은 이미 192까지 탐색하여 9가 제일 큰 수라는 것을 확인한 후 1을 제거하고 9를 확보한 후에 29에 대해서 같은 과정을 반복하게 되어있기 때문에 비효율 적이다 !
스택을 이용하여 처음이거나, 앞의 문자보다 작다면 스택에 넣어준다. 하지만 앞의 문자보다 크고, k가 아직 0이 아니라면 반복하여 앞의 문자를 제거해준다. 그리고 현재 문자를 넣어준다. 결과적으로 k개가 제거되거나, 앞에가 이미 큰 숫자들이었다면 뒤의 문자들은 들어가지 않게 되면서 최종결과대로 스택에 문자가 쌓이게 된다.
개선된 풀이 코드
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);
}
}위에 언급한 방법으로 풀이된 코드를 가져왔다. ( 이거 문제 풀어야만 볼 수 있는데 포스팅 해도 되겠쥬 ? 혹시 문제된다면 댓글.. 달아주세오.. ) 같은 방식으로 내가 코드를 새로 짜보면서 느꼈는데 한 줄 한 줄 이유가 있는, 필요 없는 줄이 하나도 없는 코드다 요곤.. 내가 짜도 비효율적이거나 예외 잡고나면 이거랑 똑같이 나온당.. 정말 최적화 되어있는 코드 ! 괜히 좋아요 많이 받은 게 아니다 !
추가 정보
+) 원래 내 풀이대로 문제를 풀 때, 문자열에서 특정 index의 문자를 제거하는 방법을 찾아보았다. 나는 따로 사용하지 않아서 기록만 해두려고 한다. String builder의 deleteCharAt()함수를 이용하면 된다. 또한 여러개의 문자를 삭제할 경우에는 delete()라는 함수도 존재한다.
