알고리즘/알문풀(백준, 프로그래머스, 코드트리)
[알고리즘] BOJ 2812 크게 만들기 (JAVA)
ragabys
2024. 6. 22. 12:44
https://www.acmicpc.net/problem/2812
백준 골드3 난이도의 문제로, 문제 지문을 읽어보면 그리디의 느낌이 많이 났던 문제였다.
K개의 숫자를 지우고 새로 만든 숫자가 최대가 되게 하는 것이 문제였는데,
숫자를 재배치하지 않기 때문에 앞쪽의 위치한 숫자가 가능한 만큼 큰 숫자를 배치해야 했다.
비교하면서 최대한 큰 수들을 앞쪽에 배치하도록 하기 위해서 stack 방식으로 맨 위의 값을 비교하며 stack에 넣어주는 형태를 사용했고,
스택 방식으로 작동하지만 마지막 최종 값을 출력할때 용이하게 하기 위해서 자료구조 자체는 덱을 사용했다.
import java.io.*;
import java.util.*;
public class boj2812 {
static int N, K, cnt;
static String num;
static StringBuilder sb;
static Deque<Integer> stack;
public static void greedy() {
stack.add(Character.getNumericValue(num.charAt(0)));
for (int i = 1; i < N; i++) {
int next = Character.getNumericValue(num.charAt(i));
int top = stack.peekLast();
if (cnt >= K) {
stack.add(next);
continue;
}
if (top < next) {
while (cnt <K && top < next) {
cnt++;
stack.removeLast();
if (stack.isEmpty()) {
break;
}
top = stack.peekLast();
}
}
stack.add(next);
}
if (cnt < K) {
while (cnt < K) {
stack.removeLast();
cnt++;
}
}
while (!stack.isEmpty()) {
sb.append(Integer.toString(stack.poll()));
}
}
public static void pre() 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());
cnt = 0;
sb = new StringBuilder();
stack = new ArrayDeque<>();
num = br.readLine();
}
public static void main(String args[]) throws IOException {
pre();
greedy();
System.out.println(sb);
}
}
해당 코드의 실행 시간은 다음과 같다.
