백준 19640 <화장실의 규칙>

우선순위 큐를 사용하여 계산할 수 있는지를 묻는 문제이다.

 

각각의 사원을 D를 기준으로 H를 기준으로 i를 기준으로 comparable을 이용하여 비교를 할 수 있는지 묻는 문제이다.

 

이 문제의 핵심은 즉 comparable 이다.

 

이렇게 D를 비교해준 뒤 같다면 H를 비교 그리고 같다면 줄의 번호를 비교해서 우선순위 큐에 넣어주는 게 핵심이다.

 

 

그리고 각 줄의 첫 번째 인원이 존재하면 우선순위 큐에 먼저 넣어 주는 식으로 진행했다.

 

또한 다음 우선순위 큐에서 꺼내는 것이 k와 같다면 종료를 하게 하고 아니라면 꺼내 주고 해당 줄이 비어있지 않다면 우선순위 큐에 넣어주는 식으로 진행했다.

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static class K implements Comparable<K>{
		int D;
		int H;
		int i;
		int num;
		public K(int d, int h, int i,int num) {
			super();
			D = d;
			H = h;
			this.i = i;
			this.num=num;
		}
		@Override
		public int compareTo(K o) {
			// TODO Auto-generated method stub
			if(this.D<o.D) {
				return 1;
			}
			else if(this.D==o.D) {
				if(this.H<o.H) {
					return 1;
				}
				else if(this.H==o.H) {
					return this.i-o.i;
				}
				else
					return -1;
			}
			return -1;
		}
		
	}
	static int N,M,k,count;
	static Queue<Integer> q[];
	static PriorityQueue<K> pq;
	static int map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		pq=new PriorityQueue<K>();
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		map=new int[N][2];
		q=new LinkedList[M];
		for(int i=0;i<M;i++) {
			q[i]=new LinkedList<Integer>();
		}
		int where=0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			map[i][0]=Integer.parseInt(st.nextToken());
			map[i][1]=Integer.parseInt(st.nextToken());
			q[where].add(i);
			where=(where+1)%M;
		}
		for(int i=0;i<M;i++) {
			if(!q[i].isEmpty()) {
				int next=q[i].remove();
				pq.add(new K(map[next][0],map[next][1],i,next));
			}
		}
		while(pq.peek().num!=k) {
			K next=pq.remove();
			count++;
			if(!q[next.i].isEmpty()) {
				int nextk=q[next.i].remove();
				pq.add(new K(map[nextk][0],map[nextk][1],next.i,nextk));
			}
		}
		System.out.println(count);
	}

		
}