[백준/BOJ] 2812번 : 크게 만들기 (JAVA / 자바)
안녕하세요~ 코딩하는 코알못 코메인입니다.
https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
- 문제 -
난이도 골드 4 문제이다.
자바에서 입력방식은 scanner와 bufferedreader가 있다.
자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.
bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.
더 자세한 내용은 아래 글 참고 하면 좋다.
(JAVA / 자바) Scanner 와 Bufferedreader
안녕하세요~ 코딩하는 코알못 코메인입니다. 이번엔 백준 문제 풀면서 계속 언급될 scanner와 bufferedreader에 대한 간단한 정리를 해볼거다. 자바에서 입력은 scanner와 bufferedreader가 있다. 우선 각자
comain.tistory.com
풀이 방법
덱 을 사용해서 풀었따.
1. 두번째줄에 입력받는 값을 문자열로 받는다.
2. 문자열에 0인덱스에 저장된 값을 덱에 저장한다.
3. 덱의 마지막에 저장되어있는 값과 문자열에서 최근에 확인한 인덱스의 다음 인덱스를 비교한다.
4. 덱의 마지막에 저장된 값이 더 작다면, 현재 확인중인 문자열의 인덱스의 값보다 덱의 마지막 값이 더 큰 값이 올때까지 마지막에 저장된 값을 제거해 준다.
5. 제거해 줄때마다 제거해줘야할 개수 count에 -1을 해준다.
6. 제거는 count가 0이 되기 전까지이거나, 덱이 비어있지 않을 경우에만 해준다.
7. 반복문이 끝나면, 덱에 저장된 값을 출력해준다.(주의 할 점은 count가 0이 아닐 경우에 제거가 다 되어진 것이 아니기때문에 맨 앞에 저장되어있는 값부터 길이 - count의 개수만큼만 출력해준다.)
예를 들어보자.
7 3
1234567일 경우.
우선 덱에 0인덱스 값인 1을 저장한다.
덱의 마지막 값은 1. 문자열(1234567)의 1인덱스 값은 2.
덱이 더 작기 때문에 마지막 값을 제거하고, count에 -1을 해준다. 덱에 저장된 값이 없거나, count가 0이 될때, 또는 덱에 저장된 마지막 값이 1인덱스보다 더 큰 값이 올때까지 제거를 반복해준다.
덱에는 1만 저장되었기에 덱에서 1을 제거하고 count -1 한번만 해준다.
제거가 끝났으면 1인덱스 값을 덱에 저장.
이제 빠르게 넘어가보자.
덱 : 2. count : 2. 문자열의 2인덱스 값 : 3.
덱에 2 제거. count -1. 덱에 3 저장.
덱 : 3. count : 1. 문자열의 3인덱스 값 : 4.
덱에 3 제거. count -1. 덱에 4저장.
count가 0이 되었다. 그럼 더이상 제거가 불가능하니. 나머지 값들을 순차적으로 덱에 저장.
덱 : 4 5 6 7
출력값 4567 이 된다.
다른 예제도 보자.
8 3
87654321
덱 : 8. count : 3. 문자열의 1인덱스 값 : 7.
덱이 더 크다. 덱에 7 저장.
덱 : 8 7. count : 3. 문자열의 2인덱스 값 : 6.
덱에 6 저장.
덱 : 8 7 6. count : 3. 문자열의 1인덱스 값 : 5.
값을 보면 계속 작은 값들만 온다. 그렇게 되면 제거없이 전부 덱에 저장되어지는데.
이럴경우 count에 값이 남으니 마지막에 출력할때 덱의 길이 - count한 만큼의 개수의 값만 출력한다.
덱 : 8 7 6 5 4 3 2 1. count : 3. 덱의 길이 8.
출력은 (8 - 3)인 5개만 맨 앞부터 출력. 출력 값은 87654이다.
마지막으로 한가지만 더 보자.
10 4
2222111113
덱 : 2. count : 4. 문자열의 1인덱스의 값 : 2.
같으면 그대로 저장. 덱에 2를 저장.
덱 : 2 2. count : 4. 문자열의 2인덱스의 값 : 2.
덱에 2 저장.
덱 : 2 2 2. count : 4. 문자열의 3인덱스의 값 : 2.
덱에 2 저장.
덱 : 2 2 2 2. count : 4. 문자열의 4인덱스의 값 : 1.
덱이 더 크니. 덱에 1 저장.
덱 : 2 2 2 2 1. count : 4. 문자열의 5인덱스의 값 : 1.
덱에 1 저장.
보면 알겠지만 2를 반복한 것처럼 같은 값은 저장만 한다. 1은 5개가 있다. 전부 반복했다 치고 스킵하자.
덱 : 2 2 2 2 1 1 1 1 1. count : 4. 문자열의 9인덱스의 값 : 3.
덱이 더 작다. 덱 마지막에 저장된 값 1을 제거. count -1.(앞에서 말한 제거 조건을 충족하는 한 반복한다.)
덱 : 2 2 2 2 1 1 1 1. count : 3. 문자열의 9인덱스의 값 : 3.
덱 마지막에 저장된 값 1을 제거. count -1.
덱 : 2 2 2 2 1 1 1. count : 2. 문자열의 9인덱스의 값 : 3.
덱 마지막에 저장된 값 1을 제거. count -1.
덱 : 2 2 2 2 1 1. count : 1. 문자열의 9인덱스의 값 : 3.
덱 마지막에 저장된 값 1을 제거. count -1.
덱 : 2 2 2 2 1. count : 0. 문자열의 9인덱스의 값 : 3.
제거 가능한 횟수가 0이다. 이제 남은 값들을 다 덱에 저장해 준다.
덱 : 2 2 2 2 1 3.
출력값은 222213이다.
3가지의 예제를 다 이해했다면 틀리는 경우는 거의 없을 것이다.
코드를 보자.
-풀이-
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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());
Deque<Character> deq = new LinkedList<Character>();
StringBuilder sb = new StringBuilder();
int count = K;
String S = br.readLine();
//시작 값을 저장.
deq.offer(S.charAt(0));
//0인덱스 값은 이미 저장 했으니 1인덱스부터 반복
for(int i = 1; i < N; i++) {
char ichar = S.charAt(i);
//덱의 마지막 값이 작으면 조건들이 충족되는 한 계속 제거.
while(deq.getLast() < ichar && count != 0) {
deq.pollLast();
count--;
//덱이 비게되면 반복 종료
if(deq.isEmpty()) break;
}
deq.offer(S.charAt(i));
}
int size = deq.size();
//count에 값이 남아있을 수도 있기에 count값을 제외한 개수만큼만 출력
for(int i = 0; i < size - count; i++) {
sb.append(deq.pollFirst());
}
System.out.println(sb);
}
}-결과-
아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.