[JAVA] 프로그래머스 - 큰 수 만들기

문제내용

https://programmers.co.kr/learn/courses/30/lessons/42883?language=java

코딩테스트 연습 - 큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

문제 접근 방법

주어진 수에서 k개의 수를 빼서 최댓값을 만드는 문제이다.

그래서 k개의 수를 언제 빼야 최댓값을 만들수 있는지 생각해봤고,

 

첫번째로 들었던 생각은 앞자리가 크면 클수록 최댓값이 되기 때문에 주어진 수에서 앞자리와 뒷자리를 비교하여 현재 뒷자리수가 앞자리수보다 크다면 앞자리수를 제거하는 방식으로 풀어야 겠다고 생각했다.

 

그리고 문자를 하나 제거하게 되면 다시 새로만들어진 문자를 처음부터 탐색하면서 첫번째 과정을 k번 만큼 반복하게 된다면 가장큰 자릿수가 나올것이라 보고 코드를 작성했다.

단, 999, 98777432 같은 경우 모든수의 크기가 같거나 앞자리가 더큰 경우도 생각해야 했고, 이를 위해 첫번째 과정에서 문자가 제거 되지 않았다면 위와같은 경우이기 때문에 문자열을 뒤에서부터 k개만큼 잘라준경우가 최댓값이 된다.
그리고 시간초과 때문에 만약 현재 탐색하는 앞자리 수가 9일땐 더이상 탐색하지 않는 방식으로 작성했다.

 

이를 고려하여 문제를 풀었고, 프로그래머스에서 정답은 맞았지만 사실 나는 내 코드에서 문제점이 있다는걸 안다.

풀이를 보면 알겠지만 1999와 같은 경우에 문제가 발생한다... k=2일때를 생각해보면 99가 나와야 하지만 무한루프 속에 빠져서 99가 나오지 않는다. 이를 해결하기 위해 1을 제거후 999가 됐을때 9를 하나제거 하는 알고리즘을 짤수는 있지만 그렇게 되면 시간초과가 뜬다. 결국 내 코드는 수정이 필요하고 좀더 콤팩트한 로직이 필요하다고 생각한다.

 

해서 내가 풀었던 풀이와 다른사람이 푼 풀이를 같이 올리려한다.

풀이를 보자.

 

---

풀이

내코드

public class Solution {
	public static String solution(String num, int k) {
		StringBuilder sb = new StringBuilder();
		int len = sb.append(num).length();
		
		while(k>0) {
			for(int j=0; j<sb.length()-1; j++) {
				if(sb.charAt(j)=='9') {continue;}
				if(sb.charAt(j)<sb.charAt(j+1)) {
					sb.deleteCharAt(j);		
					k--;
					break;
				}
			}
			if(len == sb.length()) {
				sb.delete(len-k, len); 
				break;
			}
		}
		return sb.toString();
	}
}

 

 

다른 사람 풀이

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);
    }
}

 

---

마치며

풀이는 간단하기 때문에 따로 주석을 달지는 않았다. 하지만 앞서 말했다시피 내코드에선 1999 , 2 같은 입력값이 주어질 경우 안풀리는 문제점이 있는 코드이다.

그리고 다른 사람의 풀이를 보면 훨씬 효율적이고 좋은 코드이다. 보면 알겠지만 앞의 수만 큰수로 유지하는 방법이다.

여튼 나는 내코드를 다시보고 수정해보고 안되면 다른 사람 풀이로 다시 풀어볼 생각이다.