[프로그래머스] 큰 수 만들기 (그리디)

문제 소개

큰 수 만들기 - 프로그래머스 문제를 정리합니다.
이 문제는 숫자에서 k개의 수를 제거해 만들 수 있는 가장 큰 수를 구하는 문제입니다.

문제 링크: 큰 수 만들기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 앞자리부터 순차적으로 숫자를 보며 더 큰 수가 나오면 앞 수를 제거
2. 제거 횟수 k를 다 쓸 때까지만 위 과정을 반복
3. 제거된 결과를 스택에 저장하고, 필요한 길이만큼 결과 추출

---

해결 과정 및 코드

핵심 아이디어

1. 앞에서부터 숫자를 보며, 스택 top 값이 현재 값보다 작고, 제거 횟수 k가 남아있다면 top을 제거
2. 이 과정을 반복하면서 스택에 가능한 큰 수를 남김
3. 다 끝난 후에도 k가 남아 있다면, 가장 끝의 값들을 무시해야 하므로 deque.size() - k > 0만큼만 결과에 포함

코드

시간 복잡도 : O(N)
이유: 각 문자는 최대 한 번 추가/제거됨

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for (int i = 0; i < number.length(); i++) {
            char now = number.charAt(i);
            while (!deque.isEmpty() && deque.peek() < now && k > 0) {
                deque.pop();  // 앞자리 제거
                k--;
            }
            deque.push(now);  // 현재 숫자 추가
        }

        // 필요한 개수만큼 결과에 담기 (뒤에서부터 꺼냄)
        while (deque.size() - k > 0) {
            answer.append(deque.pollLast());
        }

        return answer.toString();
    }
}