[백준]JAVA - 19640번: 화장실의 규칙

https://www.acmicpc.net/problem/19640

19640번: 화장실의 규칙

🔶 풀이

각 줄에서 맨 앞에 있는 사람끼리 비교해야하는 문제.

 

1. M개의 줄로 나눠서 WaitLine 배열리스트에 사원들을 입력해준다.

ArrayList<Line>[] waitLine = new ArrayList[M];
		
for (int i=0; i<M; i++) {
    waitLine[i] = new ArrayList<>();
}
		
for (int i=0; i<N; i++) {
    st = new StringTokenizer(br.readLine());
			
    int d = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());
    boolean deca = false;
			
    if (i == K) deca = true;
    waitLine[i%M].add(new Line(d, h, i%M, deca));
}

 

2. 각 줄에서 맨 앞에 있는 사람을 우선 순위 큐에 넣어준다.

for (int i=0; i<M; i++) {
    if (!waitLine[i].isEmpty()) {
        pq.add(waitLine[i].remove(0));
    }
}

 

3. 우선 순위 큐에서 하나씩 빼주면서 데카를 찾아주면 된다.

int ans = 0;
    while (!pq.isEmpty()) {
        Line outPerson = pq.poll();
		
        // 데카일 경우
        if (outPerson.deca) {
            System.out.println(ans);
            return;
        }
		
        // 빠져나온 줄에 사람이 있는 경우
        if (!waitLine[outPerson.line].isEmpty()) {
            pq.add(waitLine[outPerson.line].remove(0));
        }
			
    ans++;
}

빠져나온 줄에 사람이 있는 경우에 우선 순위 큐에 입력해주면 된다. 우선 순위 큐 특성상 자동으로 compareTo 에서 재정의 해준 규칙에 따라서 매번 정렬된다.

 

<최종코드>

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

public class Main {
    public static class Line implements Comparable<Line> {
        int day, urgent, line;
        boolean deca;
		
        public Line (int day, int urgent, int line, boolean deca) {
            this.day = day;
            this.urgent = urgent;
            this.line = line;
            this.deca = deca;
        }
		
        public int compareTo (Line o) {
            if (this.day == o.day) {
                if (this.urgent == o.urgent) {
                    return this.line - o.line;
                }
                return o.urgent - this.urgent;
            } else {
                return o.day - this.day;
            }
        }
    }
	
    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 M = Integer.parseInt(st.nextToken()); // 사장이 지시한 새로운 줄의 수
        int K = Integer.parseInt(st.nextToken()); // 자신의 앞에 서 있던 사원의 수
		
        PriorityQueue<Line> pq = new PriorityQueue<>();
        ArrayList<Line>[] waitLine = new ArrayList[M];
		
        for (int i=0; i<M; i++) {
            waitLine[i] = new ArrayList<>();
        }
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
			
            int d = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            boolean deca = false;
			
            if (i == K) deca = true;
            waitLine[i%M].add(new Line(d, h, i%M, deca));
        }
		
        for (int i=0; i<M; i++) {
            if (!waitLine[i].isEmpty()) {
                pq.add(waitLine[i].remove(0));
            }
        }
		
        int ans = 0;
        while (!pq.isEmpty()) {
            Line outPerson = pq.poll();
			
            // 데카일 경우
            if (outPerson.deca) {
                System.out.println(ans);
                return;
            }
			
            // 빠져나온 줄에 사람이 있는 경우
            if (!waitLine[outPerson.line].isEmpty()) {
                pq.add(waitLine[outPerson.line].remove(0));
            }
			
            ans++;
        }
    }
}