99클럽 코테 스터디 20일차 TIL - [프로그래머스] 큰 수 만들기 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 큰 수 만들기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42883

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 문자열 형식의 숫자 number, 제거할 k개의 수 (number ≤ 1,000,000, 2 ≤ number.length, 1 ≤ k ≤ number.length)
출력 : number에서 k개의 수를 제거했을 때 만들 수 있는 가장 큰 숫자

가능한 시간복잡도

O(n)

알고리즘 선택

그리디

📌 코드 설계하기

1. 숫자를 저장할 스택을 생성한다.
2. 스택이 비어 있지 않고, 제거할 수 있는 숫자가 남아 있으며, 스택의 최상단 숫자가 현재 숫자보다 작을 때 최상단 숫자를 제거해 더 큰 숫자를 만든다.
   3.현재 숫자를 스택에 추가한다.
3. 모든 숫자를 탐색한 후에도 제거해야할 숫자가 남아있으면 스택의 끝에서부터 숫자를 제거해 뒤쪽 숫자가 상대적으로 작은 경우를 처리한다.
4. 스택에 있는 숫자들을 모아 최종 문자열을 생성해 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;


public class Solution {
    public String solution(String number, int k) {
        int length = number.length();  // 주어진 숫자 문자열의 길이
        Stack<Character> stack = new Stack<>();  // 숫자를 저장할 스택
        
        for (int i = 0; i < length; i++) {
            char currentDigit = number.charAt(i);  // 현재 탐색 중인 숫자
            
            // 스택이 비어 있지 않고, 제거할 수 있는 숫자가 남아 있으며,
            // 스택의 최상단 숫자가 현재 숫자보다 작을 때
            // 스택의 최상단 숫자를 제거하여 더 큰 숫자를 만듦
            while (!stack.isEmpty() && k > 0 && stack.peek() < currentDigit) {
                stack.pop();
                k--;
            }
            
            stack.push(currentDigit);  // 현재 숫자를 스택에 추가
        }
        
        // 만약 아직 제거해야 할 숫자가 남아 있으면 스택의 끝에서부터 제거
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // 스택에 있는 숫자들을 하나의 문자열로 만듦
        StringBuilder result = new StringBuilder();
        for (Character digit : stack) {
            result.append(digit);
        }
        
        return result.toString();  // 결과를 문자열로 반환
    }
}