[JAVA] 백준 2812번 크게 만들기 자바 풀이

in STUDY / PS

스택을 활용한 그리디 문제입니다.

📚 문제

🔗 문제 링크

백준 2812번: 크게 만들기

📖 문제 설명

  • N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제
  • 입력으로 주어진 숫자에서 K개의 수를 제거했을 때 얻을 수 있는 가장 큰 수를 출력

🔍 입력 조건

  • 첫째 줄에 N과 K가 주어짐 (1 ≤ K < N ≤ 500,000)
  • 둘째 줄에 N자리 숫자가 주어짐
  • 입력되는 숫자는 모두 자연수임

🔍 출력 조건

  • 입력으로 주어진 숫자에서 K개의 수를 지웠을 때 얻을 수 있는 가장 큰 수를 출력

🧩 문제 분류

  • 알고리즘: 그리디(Greedy), 스택
  • 자료구조: 스택(Stack), 문자열
  • 난이도: GOLD III

🚀 접근 방법

  1. 스택을 사용하여 숫자들을 관리
  2. 현재 숫자가 스택의 top에 있는 숫자보다 크다면, K가 남아있는 한 pop
  3. 최종적으로 N-K 자리의 가장 큰 수를 구함

💻 구현

/**
 * BAEKJOON ONLINE JUDGE
 * 문제 이름 : 크게 만들기
 * 문제 번호 : 2812
 * 난이도 : GOLD III
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
    static int N, K;
    static char[] nums;

    // 구현
    public static String simulate(){
        Stack<Integer> stack = new Stack<>();

        // 각 글자 탐색
        for (int i = 0; i < nums.length; i++){
            // int로 변환
            int curr = Character.getNumericValue(nums[i]);

            // 현재 값과 stack top에 있는 값을 비교해서 더 큰 값이 맨 앞에 들어가도록 pop
            while (!stack.isEmpty() && stack.peek() < curr && K != 0){
                stack.pop();
                K--;
            }

            // 현재 값은 항상 stack에 넣음
            stack.push(curr);
        }

        // K개가 다 지워지지 않았다면, K개 지워질 때 까지 pop
        while( K > 0 ){
            stack.pop();
            K--;
        }

        // stack을 string으로 매핑 (최대 길이가 500000)
        String result = stack.stream()
                .map(String::valueOf)
                .collect(Collectors.joining());

        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        String s = br.readLine();
        nums = s.toCharArray();
        System.out.println(simulate());
    }
}

⏱ 시간 복잡도

  • O(N): 각 숫자는 최대 한 번씩만 스택에 들어가고 나옴

💾 공간 복잡도

  • O(N): 스택에 최대 N개의 숫자가 저장될 수 있음

📝 회고

  • 이런 유형의 문제는 스택을 활용하면 효율적으로 해결할 수 있다는 걸 배움