문제 📕

(https://www.acmicpc.net/problem/1966)

접근 방법 🧐

아니 이게 실버3..? 내가 어렵게 생각하고, 어렵게 풀었던건지 최소 실버1정도는 되는 것 같은데..🥲

이 문제는 사실 3달 전에 푼 문제다.. 근데 그때도 하루종일 끙끙대다가 맥주 한 캔의 힘으로 풀었었다. 이번에는 맨정신으로 풀어서 그런지 다시 푸는 문제임에도 한 2시간 걸렸고, 어쩔 수 없이 과거의 나에게 도움을 청했다ㅠㅠㅠㅠ

---

일반적인 우선순위큐 문제라고 생각하고 for문을 돌려서 출력하는 문제인가 싶었는데..? 아니다
그래서 여러가지 방법을 생각해봤다.

1. 입력할 때 오름차순 정렬한 Priority Queue에도 넣고, 일반 queue에도 넣은 후,
   각각 중요도를 비교하며 값을 찾아낸다.

2. map<현위치, 중요도> 을 큐에 넣는다
   ➡️ 할 수는 있을 것 같지만, poll 할 때 힘들 것 같다.

3. map과 같은 개념으로 (현위치, 중요도)를 담는 객체를 Queue에 넣어준다

➡️ 3번을 바탕으로 1번처럼 비교하는 방식으로 채택!

Integer 와 int 배열의 차이

중요도만을 담는 wOrder 배열을 만들었다. 중요도를 내림차순으로 정렬 후에 값이 담겨져있는 큐와 비교할 것이다.
내림차순으로 정렬하려는데 아 int[] 는 sort 안되던가...?
Integer 배열을 써줬다.

int와 Integer는 무엇이 다른가

• int : 산술 연산이 가능하고, null로 초기화할 수 없다
• Integer : 산술 연살이 불가능하지만, null 값을 처리할 수 있다. 객체 간 비교가 필요할 때 사용한다

사실 int[] 로 선언하고 반복문 돌리면서 내림차순으로 만들어줄 수 있지만 Arrays.sort 쓰고 싶어서 방법을 찾다가 알게된 Integer 배열이다. 이 문제 풀 때만 쓰고 다른 문제에서는 써본적 없는 것 같다 🙄

내가 쓴 코드 ✍️

import java.io.*;
import java.util.*;


class Docu{ //프린트할 문서 정보를 담는 객체
	int index, weight;
	
	public Docu(int index, int weight) {
		super();
		this.index = index; //현 위치
		this. weight = weight;//중요도 
	}
}

public class Main {
	static Queue<Docu> queue;
	static int N, M;
	static int result; //그래서 찾아야하는 M문서가 몇번째로 출력되는건데!

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int i=0;i<T;i++) {
			queue = new LinkedList<>();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); //문서 수
			M = Integer.parseInt(st.nextToken()); // 찾아야하는 것의 현 위치
			
			Integer[] wOrder = new Integer[N]; //중요도만 들어가는 배열
			st = new StringTokenizer(br.readLine());
			
			for(int j=0;j<N;j++) {
				int weight = Integer.parseInt(st.nextToken()); //중요도, 입력값
				queue.offer(new Docu(j,weight));//(현위치, 중요도) 큐에 넣어줌
				wOrder[j] = weight;
			}
			
			Arrays.sort(wOrder, Collections.reverseOrder()); //내림차순으로 정렬
			findDocu(wOrder);
			sb.append(result+"\n");
		}
		
		bw.write(sb+"");
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void findDocu(Integer[] wOrder) {
		int cnt = 0; // M이랑 같을 때까지 올려줄거
		int i=0; //내림차순으로 정렬한 프린트물 인덱스
		
		while(!queue.isEmpty()) {
			Docu d = queue.poll(); // 맨앞에 있는 거 뺀다
			
			if(d.weight < wOrder[i]) { //중요도가 낮으면 뒤로 보내준다
				queue.offer(d);
			}
			else {
				cnt++; //프린트했다
				i++; //다음으로 중요도 높은 프린트물을 찾아야한다
				if(d.index == M) { //만약 뽑아낸게 찾아야하는 것과 같다면
					result = cnt;
					return;
				}
			}
		}
	}
}

느낀점 📖

좀 더 쉬운 방법 없을까 싶어서 다른 분들 풀이를 구글에 검색해봤는데, 배열을 큐에 넣어서 푼 분들이 많이 보였다. 근데 난 왜 저게 이해가 안 가지.. 프로젝트 할 때마다 느끼지만, 내 코드 말고 남의 코드를 읽고, 빠르게 이해하는 것도 연습해야겠다.