[BAEKJOON]1946 신입 사원

문제 요약

• 알고리즘 분류: 그리디, 정렬
• 난이도:Silver1
• 문제내용:
  • T개의 테스트 케이스가 있고 각 테스트 케이스 마다 N개 응시자가 있다.
  • 각 응시자는 필기, 면접 등수로 매긴다.
  • 필기, 면접 둘중하나가 다른 응시자 보다 괜찮은 사람을 하나씩 출력해라.

• 사이트: https://www.acmicpc.net/problem/1946

1946번: 신입 사원

문제풀이

 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

 각 사원마다 다른 사원이랑 면접자 비교할려면 이중 for문으로 풀어야한다. 그러면 시간복잡도상 O(n^2)시간이 나오고  최대 인원수는 10만이기 때문에 시간 초과가 나올것이다. 그러면 정렬까지해서 O(n)안으로 처리하는 방법을 생각해야한다.

 방법은 간단하다 일단 필기, 면접 둘중 하나 기준으로 정렬한다. 그리고 그 기준의 정렬된 첫번째의 다른 것으로 커트라인 기준으로 정하고  그 다음 순위의 다른 응시 순위와 커트라인 순위를 비교해서 낮으면 합격자수를 +1해주고 커트라인 순위를 현재 순위로 변경한다. 예를 들어 필기 기준으로 먼저 정렬을 한 다음 필기 점수 1등인 사람의 면접 순위를 커트라인으로 잡고 2등 부터 면접 순위와 비교하면서 낮으면 2등의 면접순위를 커트라인으로 잡으면서 합격자수를 구하면된다.

초록색은 합격자

 2번테 테스트케이스에서 필기 위주로 정렬 한 표이다. 위 표를 예시로 들겠다.

필기 1위는 면접 4위이다. 4위를 커트라인으로 잡으면 된다. 그다음 필기 2위는 면접 5위이다 커트라인 미만이라서 탈락이다. 3위도  면접 커트라인 안되서 탈락이다. 그 다음 4위를 보면 면접은 2위이다.  2위를 커트라인을 잡고 면접 2위 미만인 응자자는 필기 6위한사람이다. 

 위 예시대로 커트라인 미만인 사람을 찾고 그 사람을 커트라인으로 잡으면서 진행하면된다.

정리

1. 리스트/ 배열로 저장한 다음 정렬한다.
2. 정렬 기준으로 1등인 사람의 다른 순위를 커트라인으로 잡는다.
3. 정렬 기준으로 2등 부터 다른 응시한 순위 커트라인 미만인 순위를 찾는다.
4. 커트라인 미만인 순위를 찾았으면 합격자수를 +1해주고 그 순위를 커트라인으로 한다.

Code

Python

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    gradles = []
    for _ in range(N):
        gradles.append(list(map(int, input().split())))

    gradles.sort()
    top = gradles[0][1]
    count = 1
    for gradle in gradles[1:]:
        if gradle[1] < top:
            count += 1
            top = gradle[1]
    print(count)

Java

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] gradles;
		int N, top, count;
		while(T-- > 0) {
			N = Integer.parseInt(br.readLine());
			gradles = new int[N][2];
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				gradles[i][0] = Integer.parseInt(st.nextToken());
				gradles[i][1] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(gradles, (o1, o2) -> o1[0] == o2[0]? o1[1] - o2[1] : o1[0] - o2[0]);
			top = gradles[0][1];
			count = 1;
			for(int i = 1; i < N; i++) {
				if(gradles[i][1] < top) {
					count++;
					top = gradles[i][1];
				}
			}
			System.out.println(count);
		}
	}
	
}