[백준] 19640번 화장실의 규칙 자바 코드 및 문제풀이 방법

[백준] 19640번 화장실의 규칙 자바 코드 및 문제풀이 방법

 

문제설명

* 더 구체적인 예시는 아래 힌트를 확인하면 된다.

 

 

생각해야 할 요소

1. 사람들을 차례대로 M개의 라인으로 집어넣어야 한다. 

2. 비교를 할 대상은, M개의 라인 중 첫번째에 위치한 사람들이다. 

    2-1. 비교 기준은, 고용기간이 오래된 사람

    2-2. 고용기간이 같다면, 화장실이 급한사람

    2-3. 같다면, line의 숫자가 앞에 있는 것 순서이다.

 

문제풀이 방법

1. 사람들을 차례대로 M개의 라인으로 집어 넣기 위해서 LinkedList[] 배열을 만들어서, 차례대로 넣어주었다.

2. pq에 조건에 해당하는 것을 Comparator 을 사용하여 정렬해주었다.  

 

문제에서 요구하는 것은 

PQ를 적절히 사용할 수 있는지, PQ를 본인의 입맛에 맞게 변경할 수 있는지 ( Comparator or  Comparable 을 사용할 수 있는지) 를 보는 것이다.

 

또한, 처음 줄서있던 사람들을 M개의 Line으로 나눌 수 있어야한다. 

LinkedList가 아닌 다른 것들을 활용해도 가능하다. 

 

 

소스코드

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

public class RuleOfToilet_19640 {
    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());
        int cnt = 0;

        LinkedList<People>[] employee = new LinkedList[M];

        for(int i=0; i<M; i++) employee[i] = new LinkedList<>();

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            employee[i % M].add(new People(x,y,i % M, i));
        }

        PriorityQueue<People> waitingPeople = new PriorityQueue<>(new Comparator<People>() {
            @Override
            public int compare(People o1, People o2) {
                int workingDay =  o2.x - o1.x;
                if(workingDay == 0){
                    int hurry = o2.y - o1.y;
                    if(hurry == 0) return o1.room - o2.room;
                    return hurry;
                }
                return workingDay;
            }
        });

        for(int i=0; i<M; i++) {
            if(employee[i].size() == 0) break;
            People people = employee[i].remove(0);
            waitingPeople.add(people);
        }

        while (!waitingPeople.isEmpty()) {
            cnt++;
            People people = waitingPeople.poll();
            
            if(people.num == K) break;
            if(employee[people.room].size() == 0) continue;

            waitingPeople.add(employee[people.room].remove(0));
        }

        System.out.println(cnt-1);
    }

    static class People {
        int x, y, room, num;

        public People( int x, int y, int room, int num) {
            this.x = x;
            this.y = y;
            this.room = room;
            this.num = num;
        }
    }
}

 

문제링크

www.acmicpc.net/problem/19640

19640번: 화장실의 규칙