프로그래머스 | Level 2 | 큰 수 만들기

Sep 02, 2024

Published byJynn

999

Programmers | Level 2 | 큰 수 만들기

Problems

📘 Src: Programmers
🗂️ Cat: Greedy

󰧭 Description

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

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

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

 Constraints

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

󰦕 Examples

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

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        Deque<Character> stack = new LinkedList<>();  // 큰 수를 만들기 위한 스택
        
        for (int i = 0; i < number.length(); i++) {
            char next = number.charAt(i);
            
            // 현재 숫자가 스택의 최상단 숫자보다 크면 스택에서 제거
            while (!stack.isEmpty() && k > 0 && stack.peek() < next) {
                k--;              // 제거할 숫자 개수 감소
                stack.pop();      // 스택에서 제거
            }
            stack.push(next);     // 현재 숫자를 스택에 추가
        }
        
        // 여전히 제거할 숫자가 남아있는 경우, 스택에서 남은 숫자 제거
        while (k > 0) {
            k--;
            stack.pop();
        }
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());  // 스택에서 숫자를 꺼내 문자열 빌더에 추가
        }
        
        return sb.reverse().toString();  // 스택은 역순으로 쌓이므로, 결과를 뒤집어서 반환
    }
}

 Approach

이 문제는 주어진 숫자에서 특정 자릿수를 제거하여 최대값을 만드는 문제로, 탐욕 알고리즘을 사용하여 해결할 수 있습니다. 스택을 활용해 숫자를 하나씩 처리하며, 현재 숫자보다 작은 숫자들을 제거해가면서 최대값을 구성합니다.

1. 문제 분석

이 문제는 숫자 number에서 k개의 숫자를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 것입니다. 주요 요소는 다음과 같습니다:

숫자 제거: k개의 숫자를 제거하면서 최대값을 만들어야 합니다. 이때, 어떤 숫자를 제거할지 결정하는 것이 중요합니다.
Greedy 선택: 현재 위치에서 가능한 최적의 선택을 반복적으로 수행하여 전체 최적해를 찾는 탐욕 알고리즘을 사용합니다.
스택을 활용한 수의 처리: 스택을 사용해 숫자들을 저장하며, 다음 숫자를 확인할 때 스택의 최상단 숫자와 비교해 더 작은 값을 제거합니다.

2. 접근 방식

문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

스택 활용: 주어진 숫자를 하나씩 탐색하면서 스택을 사용해 최대값을 구성합니다. 스택의 최상단에 있는 숫자가 현재 숫자보다 작으면 제거하고, 새로운 숫자를 추가합니다.
탐욕적 제거: k개의 숫자를 제거할 때마다 스택의 최상단 숫자와 비교하여 더 작은 숫자를 제거함으로써 남아있는 숫자들이 최대값을 구성할 수 있도록 합니다.
남은 숫자 처리: 모든 숫자를 처리한 후에도 제거해야 할 숫자가 남아있으면, 스택에서 남은 숫자들을 제거하여 최종 결과를 완성합니다.

3. 스택을 사용한 최대값 구성

주어진 숫자 number를 왼쪽에서 오른쪽으로 순차적으로 탐색하면서, 스택을 사용해 가장 큰 숫자를 구성합니다. 이 과정에서 다음과 같은 단계를 따릅니다:

스택 초기화 및 탐색 시작: 빈 스택을 초기화하고, number의 각 문자를 차례대로 확인합니다.
스택 최상단 숫자와 비교: 현재 문자가 스택의 최상단 숫자보다 크다면, 스택의 최상단 숫자를 제거합니다. 이는 작은 숫자를 제거해 더 큰 숫자가 남도록 하여, 최대값을 만들기 위한 것입니다. 이 과정은 k개의 숫자를 제거할 때까지 반복됩니다.
현재 숫자 스택에 추가: 스택의 최상단 숫자가 현재 숫자보다 크거나 같아지면, 현재 숫자를 스택에 추가합니다. 이로써 현재까지의 최대값을 유지하게 됩니다.
제거 횟수 소진: 만약 k개의 숫자를 모두 제거했음에도 아직 숫자가 남아 있다면, 남은 숫자는 스택에 그대로 추가됩니다.

Solution.java

Deque<Character> stack = new LinkedList<>();  // 큰 수를 만들기 위한 스택

for (int i = 0; i < number.length(); i++) {
    char next = number.charAt(i);
    
    // 현재 숫자가 스택의 최상단 숫자보다 크면 스택에서 제거
    while (!stack.isEmpty() && k > 0 && stack.peek() < next) {
        k--;              // 제거할 숫자 개수 감소
        stack.pop();      // 스택에서 제거
    }
    stack.push(next);     // 현재 숫자를 스택에 추가
}

이 과정을 통해 주어진 숫자에서 k개의 숫자를 제거한 후에도, 남은 숫자들이 최대값을 구성하게 됩니다. 이 단계는 문제의 핵심 알고리즘으로, 탐욕적으로 숫자를 제거하며 가장 큰 값을 만드는 방식입니다.

모든 숫자를 탐색한 후에도 k개의 숫자를 모두 제거하지 못한 경우, 스택에서 남은 숫자들을 제거합니다. 이는 탐색 과정에서 스택에 쌓인 숫자들이 이미 충분히 크거나, 제거할 필요가 없었던 경우에 발생할 수 있습니다. 이런 경우 k가 남은 상태로 모든 숫자 탐색이 끝날 수 있으며, 이 경우 남아 있는 k개의 숫자를 스택의 최상단부터 하나씩 제거하여 최종 결과를 맞춥니다.

Solution.java

// 여전히 제거할 숫자가 남아있는 경우, 스택에서 남은 숫자 제거
while (k > 0) {
    k--;          // 남은 제거할 숫자 개수 감소
    stack.pop();  // 스택에서 최상단 숫자 제거
}

5. 결과 반환을 위한 후처리

스택에서 남아 있는 숫자들을 문자열로 변환해 결과를 반환합니다. 이때, 스택에 쌓인 숫자들은 역순으로 저장되어 있으므로, 문자열로 변환한 후에는 이를 다시 뒤집어 반환합니다.

Solution.java

StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
    sb.append(stack.pop());  // 스택에서 숫자를 꺼내 문자열 빌더에 추가
}

return sb.reverse().toString();  // 스택은 역순으로 쌓이므로, 결과를 뒤집어서 반환

󰄉 Complexity

⏳ TC: O(n)
💾 SC: O(n)

주어진 숫자 문자열을 한 번 순회하며 최대값을 구성하므로, 시간 복잡도는 O(n)입니다. 스택을 사용해 숫자를 저장하고 처리하기 때문에, 공간 복잡도 또한 O(n)입니다. 탐욕 알고리즘을 사용해 최적의 결과를 도출하는 효율적인 해결 방법입니다.

Algorithm
Greedy