[BOJ] 2812번 : 크게만들기

🔗 문제 링크

https://www.acmicpc.net/problem/2812

🤔 문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

😮 문제 접근

문제에 주어진 입력 예제는 1924이며 출력은 94가 나와야한다.

처음에 정렬하고 큰 수를 출력하는 건줄 알고 정렬하여 가장 큰 수를 출력했더니 틀렸다고 나와서 뭐가 틀렸나 했더니 순서를 지키면서 가장 큰 수를 만드는 것이었다. (지금 생각하면 그런 문제가 골드 V 일리가 없다고 생각한다.)

문제 해결의 핵심은 1) 스택에서 peek한 값과 현재 접근중인 인덱스의 값을 비교해 현재 값이 크면 스택안의 원소 값을 삭제해주는 작업을 반복한 후 2)주어진 입력의 N(길이)와 K(삭제 개수)를 뺀 사이즈만큼 스택 처음부터 출력해주면 된다.

예를 들어,N의 값이 6 K의 값이 4, 숫자 199244가 주어지면 위의 1) 작업을 진행하면 아래와 같은 과정을 통해 스택이 채워진다.

1) 작업을 통해서 pop(삭제)가 2번 이루어짐을 확인할 수 있다. 삭제 카운트가 주어진 K값만큼 지워주지 않는 경우가 있으므로, 2) 작업을 통해 스택을 가장 아래 원소부터 삭제한 후의 자릿수(N-K)까지 출력해주면 99가 나온다.

이러한 방식으로 코드를 구현하면 문제가 해결된다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_2812 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int delCount = Integer.parseInt(st.nextToken());
        int size = N - delCount;

        //원소 삭제 개수 카운팅
        int count = 0;
        String[] num = br.readLine().split("");
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < N; i++) {
            //현재 접근한 값이 스택안에 있는 값보다 크면 스택 안에 있는 값을 삭제 후 삭제카운팅 증가
            while (!stack.isEmpty() && count < delCount && Integer.parseInt(stack.peek()) < Integer.parseInt(num[i])) {
                stack.pop();
                count++;
            }
            //스택에 현재 접근 값 넣어주기
            stack.push(num[i]);
        }

        StringBuilder sb = new StringBuilder();

        //삭제 개수 카운팅이 입력 삭제 개수만큼 못지우고 나오는 경우가 있으므로 원래길이에서 삭제개수 뺀 결과 사이즈만큼 스택에서 출력
        //6 4 199244의 경우 스택엔 99244가 들어가고 삭제카운팅이 입력된 개수만큼 지우지 않기때문
        for(int i=0;i<size;i++){
            sb.append(stack.get(i));
        }
        bw.write(sb.toString());
        br.close();
        bw.close();
    }
}