프로그래머스 - 42883: 큰 수 만들기 - 자바 풀이(10번 시간초과)

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 함수를 완성하세요.

 

제한 조건

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

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

 

풀이

탐욕법을 활용해야하는 문제였다. 주어진 상황에서 최선의 선택을 해야하고 이 선택이 다음 상황에 영향을 주지 않아야한다.

큰 수를 만들기 위해선 

첫번 째 - 자릿수가 큰 수여야한다.

두번 째 -  자릿 수 마다 큰 수가 할당 돼야 한다.

따라서 주어진 k를 뺀 digit 크기의 수를 구해야하고 그 수는 왼쪽 기준 자릿 수부터 큰 수가 와야한다.

문제가 짧고 간단하여 쉬운 문제인줄 알았지만 정답을 맞추긴엔 쉽지는 않았던 것 같다. 

n 이 1,000,000자리 숫자가 시간 복잡도에 걸릴 것 같다고 예상하였지만 제출해보니 거의 다 통과돼서 맞춘 문제인줄 착각했지만, 10번에서 시간초과로 틀리게 되었다.

class Solution {
    public String solution(String number, int k) {
        int digit = number.length() - k;
        int startIdx = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = digit; i > 0; i--) {
            int tmp = 0;
            for (int j = startIdx; j <= number.length() - i; j++) {
                int num = Character.getNumericValue(number.charAt(j));
                if (tmp < num) {
                    tmp = num;
                    startIdx = j + 1;
                }
            }
            sb.append(tmp);
        }
        return sb.toString();
    }
}

 

 

 

오답노트

주어진 문제는 주어진 숫자 문자열에서 k개의 숫자를 제거하여 만들 수 있는 가장 큰 수를 구하는 것으로, 탐욕적 (Greedy) 접근 방법을 사용할 수 있다.

주어진 코드에서는 모든 가능한 경우의 수를 확인하고 가장 큰 수를 찾기 위해 두 번의 반복문을 사용하고 있다. 하지만 이러한 방식은 시간 복잡도가 O(n^2)이기 때문에 큰 입력에 대해서는 비효율적일 수 있다.

더 효율적인 방법으로는 스택(Stack) 자료구조를 사용하는 것이다. 스택을 사용하여 숫자를 차례대로 쌓아가면서 현재 숫자가 스택의 맨 위 숫자보다 크면 스택에서 맨 위 숫자를 제거하고 현재 숫자를 스택에 넣는다. 이렇게 하면 스택에는 큰 숫자가 위쪽에 위치하게 된다.

입력 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이다. 스택을 사용하여 더 효율적으로 문제를 해결할 수 있다.

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        Stack<Character> stack = new Stack<>();
        int keep = number.length() - k;
        
        for (int i = 0; i < number.length(); i++) {
            char digit = number.charAt(i);
            while (!stack.isEmpty() && k > 0 && stack.peek() < digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().substring(0, keep);
    }
}