[BOJ] 백준 2812 크게 만들기 - Python/Java

문제

2812번: 크게 만들기

해설

스택 자료구조와 그리디 알고리즘을 이용해서 풀 수 있는 문제입니다.

 

N개로 이루어진 숫자 중에서 K개를 삭제해야 하고, 주어진 숫자의 순서가 변하면 안된다는 점이 스택 자료구조를 쓸 수 있는 이유가 됩니다. 그리고 각 숫자를 삭제할 것인가 말 것인가를 결정할 때 그리디(Greedy)하게 결정할 수 있죠.

 

우선 결과로 리턴할 문자열 s와 문제에서 주어진 숫자 Num이 있다고 해보겠습니다. 그렇다면 아래 로직에 따라 s를 만들어갈 수 있습니다.

 

1) s가 빈 문자열이면 무조건 현재 Num의 숫자를 더해줍니다.

2) s가 빈 문자열이 아니고, k > 0, 그리고 s의 마지막 문자보다 현재 Num의 문자가 크다면 s의 마지막 문자열을 계속해서 제거해준 후 현재 문자를 더해줍니다.

3) 위 과정을 반복한 뒤 k가 0보다 큰 상태로 남는다면, 뒤에서부터 k개를 삭제해줍니다.

 

위 내용을 코드로 옮기면 아래와 같습니다.

 

풀이 - 파이썬

n, k = map(int, input().split())
num = input()
answer = ""
for n in num:
    if len(answer) == 0: 
        answer += n
    else:
        while(len(answer) > 0 and k > 0 and answer[-1] < n):
            answer = answer[:-1]
            k -= 1
        answer += n
if k > 0: answer = answer[:-k]
print(answer)

 

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class B_2812 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String number = br.readLine();

        Stack<Character> stack = new Stack<>();
        stack.add(number.charAt(0));
        for(int i = 1; i < number.length(); i++){
            char x = number.charAt(i);
            if(stack.isEmpty()){
                stack.push(x);
            }else{
                while(!stack.isEmpty() && k > 0 && stack.peek() < x){
                    stack.pop();
                    k--;
                }
                stack.push(x);
            }
        }

        String answer = stack.stream().map(x -> String.valueOf(x))
                .collect(Collectors.joining());
        while(k-- > 0) answer = answer.substring(0, answer.length()-1);
        System.out.println(answer);
    }
}