[백준] 2812번 크게 만들기

문제 설명

• https://www.acmicpc.net/problem/2812
• Gold 3
• 풀이시간 : 40분

문제 풀이

• 그리디한 접근과 스택 자료구조를 이용하였다.
• 먼저 특정 배열에서 1자리를 뺄 때 가장 큰 숫자를 만드는 방법은 맨 앞에서 부터 비교하며 처음 다음 자리수보다 작아지는 특정 자리를 빼주어야한다.
• 위 과정을 N번 반복하면 되지만 시간초과가 발생한다.
• O(N)풀이를 위해 스택 자료구조를 활용한다.

1. 스택에 값이 없거나 K=0이면 현재 자리수를 넣어준다.
2. 스택의 가장 첫번째 값이 현재값보다 크거나 같을때까지 스택에서 값을 빼준다(K감소도 병행)
3. 크거나 같은 값을 만나면 스택에 현재값을 넣어준다.

• 주어진 숫자의 모든 자리수에 대해 위를 반복하고 남은 K만큼 뒤에서 빼주면 가장 큰 수가 된다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static String removeCharAt(String str, int index) {
        return str.substring(0, index) + str.substring(index + 1);
    }
    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        String in = br.readLine();

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < in.length(); i++) {
            int cur = in.charAt(i) - '0';
            if (stack.isEmpty() || K == 0) stack.add(cur);
                // K남아 있으면 비교하여 넣어줌
            else {
                while (true) {
                    if (K == 0 || stack.isEmpty() || stack.peek() >= cur) break;
                    else {
                        stack.pop();
                        K--;
                    }
                }
                stack.add(cur);
            }
        }
        while(K-- > 0) stack.pop();
        if (stack.isEmpty()) bw.write("0\n");
        else {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                char cur = (char) (stack.pop() + '0');
                sb.insert(0, cur);
            }
            bw.write(sb.toString());
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 크게 만들기 (18:09)
 *
 * N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
 * 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
 * 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
 *
 * 10 4
 * 4177252841
 * 775841
 *
 * - 완전 탐색 -> 시간 초과
 * - 그리디 -> 현재 자리(a) 다음 자리수(b) 비교
 *        - a >= b -> 다음 자리로 넘어감
 *        - a < b -> 현재 자리 제거 후 K 감소
 * - 4177252841
 * - 작거나 같으면 추가
 * - 크면 해당 숫자보다 큰 숫자를 만날때까지 뺴주고 추가
 * - 7 7 8 4 1
 */