[백준] 2812 - 크게 만들기(JAVA)

1. 소요시간 : 1시간 10분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 3
4. 문제 유형 : 자료구조, 그리디 알고리즘, 스택
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2812
8. 푼 날짜 : 2023.03.17

1. 사용한 자료구조 & 알고리즘

나는 우선순위 큐를 사용했다. 문제를 풀고 다른 사람들 풀이를 봤는데 신기하게도 우선순위 큐를 써서 푼 사람이 거~~의 없었다. 대부분 스택을 이용해서 풀었다.

2. 사고과정

최대한 문제유형을 안보고 풀려고 했다. 30분째까지 문제유형을 못찾겠다면 그때 문제유형을 보기로 했다. 우선 19분 째에 문제를 어떻게 풀지 알았고, 그리고 한 40분 째에 우선순위 큐를 써야겠다고 생각했다. 처음에 우선순위 큐에 몇개를 넣어줘야하는지만 20분 고민했다. 그냥 K개 넣어주면 되는데 이걸 20분 고민하다니...

그냥 이 사진은 내가 이 문제를 풀기 위해 얼마나 사고를 많이했나? 를 기억하기 위해 첨부했다.

3. 풀이과정

1. 초기에 K개 만큼 우선순위 큐에 넣어준다.
   우선순위 큐의 기준은
   (1) 숫자가 큰 순서대로.
   (2). 인덱스가 낮은 순서대로)
2. 여기서부터 1개씩 poll해주는데 poll 한 index가 이전의 poll한 index 보다 낮아서는 안된다. 그렇다면 continue
   이 경우가 아니라면 출력한다.
3. start는 이번에 poll한 index이고, end는 계속 1씩 증가시켜준다.
4. 그리고 pq에 계속 다음 값을 1개씩 추가시켜준다.

시간복잡도는 O(nlogn) 이 걸릴 것이다.
pq에 숫자 n개를 넣는데에 O(nlogn)
pq에서 숫자 n개를 꺼내는데에 O(nlogn)
결국 더해주면 O(nlogn) 이다.

4. 소스코드

import java.io.*;
import java.util.*;
class Number implements Comparable<Number> {
	int index;
	char value;
	Number(int index,char value){
		this.index=index;
		this.value=value;
	}
	@Override
	public int compareTo(Number o) {
		// TODO Auto-generated method stub
		if(this.value < o.value) {
			return 1;
		}
		else if(this.value==o.value) {
			if(this.index>o.index)
				return 1;
		}
		return -1;
	}
	
}
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		
		PriorityQueue<Number> pq=new PriorityQueue<>();
		
		char arr[]=new char[N];
		String word=br.readLine();
		for(int i=0;i<arr.length;i++) {
			arr[i]=word.charAt(i);
		}
	
		for(int i=0;i<=K;i++) {	
			pq.add(new Number(i,arr[i]));
		}
		int start=-1;
		int end=K;
		
		
		while(true) {
			
			Number temp=pq.poll();
			int index=temp.index;
			int value=temp.value;
			
			if(index<start)
				continue;
			
			sb.append(value-'0');
			start=index;
			end++;
			if(end>=arr.length)
				break;
			pq.add(new Number(end,arr[end]));
			
			
		}
		
		System.out.println(sb);
		
	}
}

5. 결과

6. 회고

문제를 다풀고 제출할때 제발제발제바렞ㅂ랍제젭라제바 ... 하면서 싹싹 빌면서 제출했다. 이거를 틀렸으면 마음이 꺾였을 것 같다. 그리고 이 문제를 보며 느낀 게 스택을 사용한다면 더 쉽게 문제를 풀 수 있었을지도 모르겠다는 생각이 든다. 지금은 새벽이간이고 오전에 수업이 있어서 이만 잘 것 같지만 수업이 끝나면 스택을 사용해서 푼 사람들은 어떻게 풀었나 확인해 봐야겠다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212