[BOJ] 14464.소가 길을 건너간 이유 4(PQ).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

오랜만에 재미있는 

소가 길을 건너간 이유 시리즈 문제를 풀어보았다.

어디선가 많이 풀어본 문제 같기도 했는데,

역시 풀어본 비슷한 유형이라도 시간이 지나면 가물가물하다..

//

우선 최악의 경우 C * N 이 400,000,000 이라서

시간제한 2초 안에 풀릴 수 없을 줄 알았는데..

모든 경우의 수를 확인하는 건 아니라서 풀릴 수 있던 것 같다.

#. Code

해결했던 방법은 생각보다 단순하다.

우선 닭과 소의 시간을 오름차순으로 정렬해주자.

소의 시간은 end 시간 기준으로 정렬해주었다.

아래와 같은 Case의 경우를 대비하기 위해서였다.

Ti   :  2    4

Aj Bj: 1 5  2 3

핵심적인 동작은

닭들이 소들을 모두(?)확인하는 방법이었다.

line 48) 닭의 도움을 받을 수 있는 소를 발견하면 count해주고 소를 priorityQueue에서 빼주었다.

line 58) 만일 해당 소가 도움받을 수 있는 닭이 없다면 마찬가지로 priorityQueue에서 빼주었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer;   public class BOJ14464 {       static int C, N;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           C = Integer.parseInt(st.nextToken());         N = Integer.parseInt(st.nextToken());           int[] chickens = new int[C];         for (int i = 0; i < C; i++) {             chickens[i] = Integer.parseInt(br.readLine());         }           PriorityQueue<Cow> pq = new PriorityQueue<>();         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());                          pq.add(new Cow(a, b));         }                  Arrays.sort(chickens);         System.out.println(process(chickens, pq));     }         private static int process(int[] chickens, PriorityQueue<Cow> pq) {                  int cnt = 0;                  while(!pq.isEmpty()) {                          boolean isHelp = false;             for (int i = 0; i < C; i++) {                 // 닭의 도움을 받아 소가 길을 건널 수 있다면                 if(chickens[i] >= pq.peek().s && chickens[i] <= pq.peek().e && chickens[i] > 0) {                     cnt++;                     pq.poll();                     isHelp = true;                     chickens[i] = -1;                                          break;                 }             }             // 소가 도움을 받을 수 없을 경우             if(!isHelp) pq.poll();         }                  return cnt;     }         static class Cow implements Comparable<Cow> {         int s, e;           public Cow(int s, int e) {             this.s = s;             this.e = e;         }           @Override         public int compareTo(Cow o) {             if(this.e != o.e) return Integer.compare(this.e, o.e);              else return Integer.compare(this.s, o.s);         }       } } Colored by Color Scripter

cs

#. Code_v1

최적화가 잘 된 코드를 뜯어보았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer;   public class BOJ14464_v2 {       static int C, N;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           C = Integer.parseInt(st.nextToken());         N = Integer.parseInt(st.nextToken());           int[] chickens = new int[C];         for (int i = 0; i < C; i++) {             chickens[i] = Integer.parseInt(br.readLine());         }           Cow[] cows = new Cow[N];         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());               cows[i] = new Cow(a, b);         }           Arrays.sort(chickens);         Arrays.sort(cows);                  System.out.println(process(chickens, cows));     }       private static int process(int[] chickens, Cow[] cows) {           int cnt = 0, cIdx = 0;         PriorityQueue<Integer> pq = new PriorityQueue<>();                  for (int i = 0; i < C; i++) {             // 닭이 도울 수 있는 소를 찾아보자.             while(cIdx < N && cows[cIdx].s <= chickens[i]) {                 // 도울 수 있는 소의 end time을 queue에 추가                 pq.add(cows[cIdx++].e);             }                          // 닭이 도울 수 없는 소는 보내주자.             while(!pq.isEmpty() && pq.peek() < chickens[i]) {                 pq.poll();             }                          // pq에 소가 남아있다면 길을 건널 수 있게 도와주자.             if(!pq.isEmpty()) {                 cnt++;                 pq.poll();             }         }           return cnt;     }       static class Cow implements Comparable<Cow>{         int s, e;           public Cow(int s, int e) {             this.s = s;             this.e = e;         }                  @Override         public int compareTo(Cow o) {             return Integer.compare(this.s, o.s);         }     } } Colored by Color Scripter

cs

line 45~62) 닭들이 순서대로 도울 수 있는 소를 탐색한다.

line 47~50) 도울 수 있는 소를 찾는데 닭의 초가 Aj보다 크거나 같은 경우를 기준으로 찾아보자.

line 53~55) 위의 범위에 포함되는 소들 중에서 Bj가 닭의 초보다 작은 경우는 제외해준다. 

line 58~61) 위의 과정을 거치고 pq에 소가 남아있다면 가장 우선순위가 높은 소를 건너게 해준다.

 남은 소들은 다음 차례의 닭들에게 도움을 요청해본다..