[백준 - 1946] 실버1 신입 사원 (그리디)

www.acmicpc.net/problem/1946

1946번: 신입 사원

 

1. 유형

그리디

 

2. 풀이

문제를 이해하는데 오래 걸렸다.

 

서류 순으로 오름차순 정렬한다. 그 다음 면접 성적 순으로 우선순위 큐에 넣는다.

 

그러면 서류 성적은 더 낮지만 면접 성적은 더 높은 사람이 들어올 수 있다.

 

3. 코드

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

public class back_1946신입사원 {
	static class Pair implements Comparable<Pair>{
		int a,b;
		public Pair(int a,int b) {
			this.a=a;
			this.b=b;
		}
		@Override
		public int compareTo(Pair o) {
			
			return this.b-o.b  ;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.valueOf(in.readLine());
		for (int i = 0; i < T; i++) {
			int N = Integer.valueOf(in.readLine());
			int map[][] = new int[N][2];
			int answer =0;
			StringTokenizer st;
			for (int j = 0; j < N; j++) {
				st = new StringTokenizer(in.readLine(), " ");
				map[j][0] = Integer.valueOf(st.nextToken());
				map[j][1] = Integer.valueOf(st.nextToken());
			}
			Arrays.sort(map, new Comparator<int[]>() {
				@Override
				public int compare(int o1[], int o2[]) {
					return o1[0]-o2[0];
				}
			}); 
			PriorityQueue<Pair> pq = new PriorityQueue<>(); 
			answer++;
			pq.add(new Pair(map[0][0], map[0][1]));
			for (int j = 1; j < N; j++) {
				if(!pq.isEmpty()) {
					Pair end = pq.peek();
					if(end.b > map[j][1]) {
						pq.add(new Pair(map[j][0], map[j][1]));
						answer++;
					}
				}
			}
			System.out.println(answer);
		}
	}
}

2차원 배열 오름차순 정렬

			Arrays.sort(map, new Comparator<int[]>() {
				@Override
				public int compare(int o1[], int o2[]) {
					return o1[0]-o2[0];
				}
			}); 

우선순위큐 클래스

	static class Pair implements Comparable<Pair>{
		int a,b;
		public Pair(int a,int b) {
			this.a=a;
			this.b=b;
		}
		@Override
		public int compareTo(Pair o) {
			
			return this.b-o.b  ;
		}
		
	}