[문제 풀이] 백준 2523번 크게 만들기 JAVA - 다시 풀어보기

문제

 

  문제접근 방법   

해당 문제는 N과 K 그리고  N자라 숫자를 입력받고 숫자 중 K개의 숫자를 제거하여 만들 수 있는 가장 큰수를 출력하는 프로그램을 작성하는 문제이다. 

문제 접근 방식은 앞자리부터 하나씩 보면서, 이전보다 작은 수가 나올 때까지 스택에서 제거하고자 한다. 가장 큰 수를 만들기 위해서는 왼쪽(앞자리)에 큰 수가 와야 한다. 따라서 숫자를 앞에서부터 하나씩 보면서 스택의 top보다 현재 숫자가 크면, 작은 숫자를 제거하는 방식으로 문제를 해결하고자함.

< 최종 코드 >

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        int k = sc.nextInt(); 
        String number = sc.next(); 

        Deque<Character> stack = new ArrayDeque<>();
        int count = k;

        for (int i = 0; i < n; i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && count > 0 && stack.peekLast() < c) {
                stack.pollLast();
                count--;
            }
            stack.addLast(c);
        }

        
        while (count-- > 0) {
            stack.pollLast();
        }

        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }

        System.out.println(sb.toString());
    }
}

먼저 입력을 받은 후 스택을 사용하여 현재까지 선택한 수들을 저장할것인데 실제로는 Stack이 아닌 Deque로 선언해 Stack의 단점을 보완하는 코드를 작성하였다. 이후 for문이 핵심인데  숫자를 왼쪽부터 한 자리씩 확인하고 while문에서 스택이 비어있지 않고

아직 지울 수 있는 숫자가 남아 있고 스택의 마지막 숫자가 현재 숫자보다 작다면 더 큰 수를 앞에 두기 위해 pop하고 이후 c를 스택에 추가하는 식이다. 아직 count > 0이면 숫자를 순회할 때는 앞자리 숫자만 고려했기 때문에 끝까지 순회했지만 아직 지운 개수가 부족한 경우가 발생할 수 있어 이경우 뒤에서부터 숫자를 제거해서 개수를 맞춰준다.