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

📌 핵심 요약

• 문제 핵심 — 숫자 문자열에서 k개를 제거해 만들 수 있는 가장 큰 수를 구함
• 핵심 아이디어 — 앞자리가 클수록 큰 수 → 새 숫자가 들어올 때 그보다 작은 직전 숫자들을 제거(그리디)
• 자료구조 — "맨 뒤를 보고 지운다"는 동작이라 스택(또는 StringBuilder) 이 딱 맞음
• 남은 k 처리 — "9876" 처럼 내림차순이면 끝까지 못 지움 → 남은 k개는 뒤에서 잘라냄

 

목차

1 문제 소개

숫자 문자열 number 에서 k개의 숫자를 제거합니다. 남은 숫자들의 순서는 그대로 유지한 채로, 만들 수 있는 가장 큰 수를 문자열로 반환하면 됩니다. 예를 들어 "1924" 에서 2개를 지우면 "94" 가 가장 큰 수입니다.

Programmers Lv.2

큰 수 만들기

number 길이 1 ~ 1,000,000

분류: 그리디

제약 조건

• number는 길이 1 이상 1,000,000 이하의 숫자 문자열.
• k는 1 이상, number의 길이 미만인 자연수.

입출력 예

• "1924", k=2 → "94"
• "1231234", k=3 → "3234"
• "4177252841", k=4 → "775841"

2 접근 방법 (그리디)

왜 "앞자리"가 중요한가

자릿수가 정해져 있으므로, 큰 수를 만들려면 앞쪽에 큰 숫자가 와야 합니다.

그래서 새로운 숫자를 하나 볼 때마다, 이미 쌓아둔 숫자들 중 맨 뒤가 지금 숫자보다 작으면 과감히 지웁니다. 

단, 지울 수 있는 횟수 k가 남아 있을 때만 가능합니다.

ℹ️

왜 "지금보다 작은 것"만 지우나?

예를 들어 쌓인 게 1 인데 다음에 9 가 오면, 앞의 1 을 지우고 9 를 앞세우는 게 무조건 이득입니다. 반대로 쌓인 게 9 인데 1 이 오면 지우지 않습니다. 즉 왼쪽에서 오른쪽으로 가면서 작은 봉우리를 깎아내는 그리디입니다.

남은 k를 어떻게 처리할까

"9876" 처럼 이미 내림차순이면 while문에서 아무것도 못 지우고 k가 그대로 남습니다.

이땐 앞에서부터는 더 키울 수 없으니, 남은 k개를 그냥 맨 뒤에서 잘라내면 됩니다.

3 풀이 1 — StringBuilder

StringBuilder 자체를 스택처럼 씁니다.

 

Java — StringBuilder 풀이

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < number.length(); i++) {
            char c = number.charAt(i);

            // 맨 뒤 문자가 지금 문자보다 작고, 지울 기회가 남았으면 제거
            while (sb.length() > 0 && k > 0 && sb.charAt(sb.length() - 1) < c) {
                sb.deleteCharAt(sb.length() - 1);
                k--;
            }
            sb.append(c);
        }

        // 남은 k개는 뒤에서 잘라냄 (substring 한 줄로 처리)
        return sb.substring(0, sb.length() - k);
    }
}

💡

substring(0, length - k) 한 줄의 미학

내림차순이라 k가 남았을 때, 별도 반복문 없이 마지막에 한 번에 잘라내는 방식입니다. 남은 처리를 따로 분기하지 않고 똑같은 흐름으로 마무리하는 점이 깔끔합니다.

4 풀이 2 — Stack

의도를 더 직접적으로 드러내는 버전입니다.

Stack 의 peek/pop/push 로 "맨 위 비교 → 제거 → 추가" 흐름을 그대로 표현합니다.

 

Java — Stack 풀이

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        Stack<Character> stack = new Stack<>();
        int length = number.length();

        for (int i = 0; i < length; i++) {
            char c = number.charAt(i);

            // 1. 스택이 비어있지 않고  2. 지울 기회(k)가 남았으며
            // 3. 맨 위 숫자가 현재 숫자보다 작으면 제거
            while (!stack.isEmpty() && k > 0 && stack.peek() < c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        // "9876"처럼 내림차순이라 k가 남았다면 뒤에서 그만큼 제거
        while (k > 0) {
            stack.pop();
            k--;
        }

        // 스택을 아래(가장 먼저 넣은 것)부터 순서대로 이어붙임
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }
        return sb.toString();
    }
}

⚠️

Stack을 for-each로 돌면 "아래→위" 순서

java.util.Stack 은 Vector 를 상속해서, for-each로 순회하면 가장 먼저 push한 것부터 나옵니다. 즉 우리가 원하는 정답 순서대로 나오므로 뒤집을 필요가 없습니다. (만약 pop() 으로 꺼내면 역순이 되어 뒤집어야 하니 주의)

5 두 풀이 비교 & 정리

알고리즘은 완전히 동일합니다(그리디 + 모노토닉 스택). 차이는 무엇으로 스택을 표현했는가와 남은 k를 어떻게 마무리했는가 뿐입니다.

구분	풀이 1 (StringBuilder)	풀이 2 (Stack)
스택 역할	StringBuilder 맨 끝	Stack의 top
남은 k 처리	substring 한 줄	while로 pop 반복
최종 문자열	이미 sb에 완성	for-each로 재조립 필요
가독성	간결함	의도가 명확
시간복잡도	O(n)	O(n)

💡

왜 O(n)인가 (while이 있는데도)

안쪽 while 때문에 느려 보이지만, 각 문자는 스택에 한 번 push되고 최대 한 번 pop될 뿐입니다. 전체 push/pop 횟수가 2n 으로 묶이므로 전체는 O(n) 입니다. (전형적인 모노토닉 스택의 상환 분석)

"1231234", k=3 으로 따라가기

예시

결과: "3234"

1. 1 → 스택 [1]
2. 2 → top 1 < 2 이므로 1 제거(k=2) → [2]
3. 3 → top 2 < 3 이므로 2 제거(k=1) → [3]
4. 1 → top 3 ≥ 1, 그대로 → [3,1]
5. 2 → top 1 < 2 이므로 1 제거(k=0) → [3,2]
6. 3, 4 → k=0이라 더는 못 지움 → [3,2,3,4] = "3234"

ℹ️

마무리

그리디는 "지금 이 선택이 왜 최선인가"를 설명할 수 있어야 합니다. 이 문제에선 "뒤에 더 큰 수가 오면 앞의 작은 수는 버리는 게 항상 이득" 이라는 한 줄이 그 근거입니다. 자료구조는 StringBuilder든 Stack이든 취향껏 고르면 됩니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.