[Python, Java] 프로그래머스 - 큰 수 만들기

문제

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

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

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

제한 조건

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

 

풀이

문제 분류 자체가 그리디로 분류되어 있어서 그리디를 활용할까 하다가 좀 더 간단하게 풀 수 있는 방법이 생각이 났습니다.

그냥 가장 큰 문자를 계속해서 찾으면 되는 방법입니다. 이때 k만큼 문자열을 제거할 예정이니까 문자열 길이 - k 만큼 반복하면 되는 방식입니다. 이 부분을 고려해서 반환할 문자열의 길이가 x라고 하면 가장 큰 문자를 찾을 때 해당 문자 뒤에 x-1만큼의 길이가 있어야 합니다.

예를 들어 문제에서 주어진 1924를 기준으로 생각해봅시다. 문자열 중 가장 큰 수는 9입니다. 큰 수 만들기 문제에선 항상 맨 앞자리 숫자가 제일 크면 장땡이기 때문에 9를 기준으로 나머지 문자열 채우면 됩니다. 앞서 얘기했던 조건을 생각해보면 9 뒤에 2개의 문자열이 더 있으니 충분히 충족됩니다. 1개를 제거하고 남은 문자열은 1개이기 때문에 마지막 숫자는 9 뒤에 있는 가장 큰 숫자인 4입니다.

이 내용 그대로 코드를 짜보면 아래와 같습니다.

def solution(number, k):
    numbers = list(map(int,number))
    answer = ''
    last = len(numbers) - k
    for i in range(len(numbers) - k):
        last -= 1
        max_value = max(numbers[:len(numbers)-last])
        max_idx = numbers.index(max_value)
        answer += str(max_value)
        numbers = numbers[max_idx+1:]
    return answer

코드가 너무 복잡해 지는 것 같아서 max_value와 max_idx와 같은 변수를 설정해 두었습니다.

1. numbers는 숫자가 들어있는 배열이고, last는 남은 문자열 수를 표현합니다.
2. 이 과정을 남은 문자열 수 만큼 반복하면서 가장 큰 숫자를 찾습니다.
3. 숫자를 찾기 전 남은 문자열 수를 하나 감소합니다.
4. numbers에서 가장 큰 값을 찾는 데, 자신의 인덱스 뒤에 남은 문자열 수 만큼이 올 수 있도록 합니다. (추가해야 할 숫자가 2개남았는데 가장 큰 숫자를 배열의 가장 마지막 요소로 찾으면 안되기 때문)
5. 답에 이 값을 추가하고, 자신의 인덱스 뒤 배열을 numbers로 새로 설정합니다.

이 방식은 2케이스에서 시간초과가 발생해서 불필요한 부분을 삭제해 개선해보았습니다.

우선 매번 max를 계산하고 리스트 슬라이싱 과정이 오래 걸릴 수 있다고 생각하여 number 문자열을 int 형 리스트로 변환하지 않았습니다. max를 사용하지 않고 가장 큰 값을 계산할 때 쉽게 사용할 수 있는 방법은 stack을 사용하는 것 입니다.

짱구 굴리다 결국 그리디로 돌아오게 되어버렸습니다..

Java

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        Stack<Character> st = new Stack<>();
        
        for (int i = 0; i < number.length(); i++) {
            char nm = number.charAt(i);
            
            // k가 0보다 크고, 스택이 비어 있지 않으며, 스택의 마지막 값이 현재 값보다 작은 경우
            while (k > 0 && !st.isEmpty() && st.peek() < nm) {
                st.pop();  // 스택의 마지막 값 제거
                k--;       // 제거할 횟수 줄임
            }
            st.push(nm);  // 현재 문자를 스택에 추가
        }
        
        // 만약 k가 남아있는 경우 스택의 끝에서 k개 제거
        while (k > 0) {
            st.pop();
            k--;
        }
        
        // 스택에 있는 숫자들을 정답 문자열로 연결
        StringBuilder answer = new StringBuilder();
        for (char ch : st) {
            answer.append(ch);
        }
        
        return answer.toString();
    }
}

Python

def solution(number, k):
    stack = []
    for num in number:
       
        while k > 0 and stack and stack[-1] < num:
            stack.pop()  
            k -= 1 
        stack.append(num)
    
    
    if k > 0:
        stack = stack[:-k]
    
    return ''.join(stack)

1. 숫자를 순회하면서 스택의 맨 위 숫자가 현재 숫자보다 작으면 스택에서 제거하고, 현재 숫자를 스택에 추가합니다. 이렇게 하면 스택에는 큰 숫자들이 순서대로 쌓이게 됩니다.
2. 숫자를 순회하면서 제거 기회(k)가 남아 있는 동안, 스택의 맨 위 숫자와 비교하여 현재 숫자가 더 크다면 스택의 숫자를 제거합니다.
3. 제거 기회를 다 사용하지 않았고 아직 남아있는 경우에는 결과적으로 뒤쪽에 있는 숫자들을 제거하는 것이 최선이므로, 스택의 마지막에서 k개의 숫자를 제거합니다.
4. 스택에 남은 숫자들을 합쳐 최종 결과를 반환합니다.

다른 풀이도 살펴보았을 때 전부 원리는 비슷해서 다른 코드는 리뷰하지 않겠습니다.