[백준 - 19640] 골드5 - 화장실의 규칙

www.acmicpc.net/problem/19640

19640번: 화장실의 규칙

 

1. 유형

우선순위큐

 

2. 풀이

 

우선순위큐에 들어갈 클래스를 만든다.

3. 코드

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 {
	static int N, M, K;

	static class Pair implements Comparable<Pair> {
		int d, h, l;
		boolean deca;

		public Pair(int d, int h, int l, boolean deca) {
			// TODO Auto-generated constructor stub
			this.d = d;
			this.h = h;
			this.l = l;
			this.deca = deca;
		}

		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			if (this.d == o.d) {
				if (this.h == o.h) {
					return this.l - o.l;
				}
				return o.h - this.h;
			}
			return o.d-this.d;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		K = Integer.valueOf(st.nextToken());
		Queue<Pair> queue[] = new Queue[M];
		for (int i = 0; i < M; i++) {
			queue[i] = new LinkedList<>();
		}
		int idx = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int d = Integer.valueOf(st.nextToken());
			int h = Integer.valueOf(st.nextToken());
			int l = idx;
			boolean deca = false;
			if (i == K)
				deca = true;
			queue[idx++].add(new Pair(d, h, l, deca));
			if (idx == M)
				idx = 0;
		}
		int num=0;
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		for(int i=0; i<M;i++) {
			if(!queue[i].isEmpty())
				pq.add(queue[i].poll());
		}
		while(true) {
			Pair cur = pq.poll();
			if(cur.deca) {
				break;
			}else {
				if(!queue[cur.l].isEmpty()) {
					pq.add(queue[cur.l].poll());
				}
			}
			num++;
		}
		System.out.println(num);
	}
}

 

4. 느낀점

처음에 시간초과가 떴는데, 

 

시간복잡도를 생각하면서 풀어야겠다.