BJ_G4_2812_크게 만들기 - Java

[문제링크]

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

2812번: 크게 만들기

---

[문제]

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

---

[입력]

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

---

[출력]

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

---

[예제 입력 1]

4 2
1924

---

[예제 출력 1]

94

---

[예제 입력 2]

7 3
1231234

---

[예제 출력 2]

3234

---

[예제 입력 3]

10 4
4177252841

---

[예제 출력 3]

775841

 

---

 

[설명]

이 문제는 스택 문제이다.

가장 큰 숫자를 최대한 앞에 써야하기 때문에 만약 전에 있는 숫자들이 지금 위치의 숫자보다 작으면 스택에서 빼주면서 minus를 하나 추가해준다.

minus가 K와 같아지면 뺄 수 있는 횟수가 없으므로 계속 스택에 남은 수들을 넣어준다.

만약 minuns가 K보다 작으면서 반복문이 종료되었을 경우, 앞에서부터 개수를 출력해준다.

 

 

 

백준 알고리즘 2812번 JAVA풀이

 

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = scann.nextInt();
		int K = scann.nextInt();
		int[] arr = new int[N];
		int[] answer = new int[N - K];
		char[] ch = scann.next().toCharArray();
		for (int i = 0; i < N; i++) {
			arr[i] = ch[i] - '0';
		}
		Stack<Integer> st = new Stack<>();
		st.add(arr[0]);
		int minus = 0;
		for (int i = 1; i < N; i++) {
			while (!st.isEmpty()) {
				if (minus == K) {
					break;
				}
				if (st.peek() < arr[i]) {
					st.pop();
					minus++;
				} else if (st.peek() >= arr[i]) {
					break;
				}
			}
			st.add(arr[i]);
		}
		if (minus < K) {
			int left = K - minus;
			for (int i = 0; i < st.size() - left; i++) {
				sb.append(st.get(i));
			}
		} else {
			for (int i = 0; i < st.size(); i++) {
				sb.append(st.get(i));
			}
		}
		System.out.println(sb.toString());
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.