문제
N명의 지원자 각각에 대해 서류 심사 순위와 면접 순위가 주어진다. 어떤 지원자가 합격하려면 다른 어떤 지원자와 비교해도 서류 순위 또는 면접 순위 중 적어도 하나가 더 높아야 한다(동점자 없음). 최대 합격 인원을 구하는 문제다.
입력
- 첫째 줄: 테스트 케이스 수 T
- 각 케이스 첫째 줄: 지원자 수 N (1 이상 100,000 이하)
- 이후 N개 줄: 서류 순위, 면접 순위
출력
각 테스트 케이스마다 최대 합격 인원을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 5 3 2 1 3 4 1 2 4 5 5 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 | 4 3 |
풀이
서류 순위 기준으로 정렬(1등부터)한 뒤, 이미 합격한 사람들 중 최소 면접 순위를 추적하여 그것보다 면접 순위가 높을 때만 합격시키는 그리디 전략을 사용한다.
- 지원자를
cnt[서류순위] = 면접순위배열에 저장한다. (서류 순위가 배열 인덱스) - 서류 1등(인덱스 1)의 면접 순위
c를 초기 기준으로 삼고 합격자 수ans = 1로 시작한다. - 서류 2등부터 N등까지 순회하며
c > cnt[i]이면, 즉 현재 지원자의 면접 순위가 현재까지 합격자 중 최고 면접 순위보다 높으면 합격시키고c를 갱신한다. - 각 테스트 케이스의 결과를
StringBuilder에 누적 후 출력한다.
핵심 아이디어: 서류 순위로 정렬하면 인덱스가 클수록 서류 순위가 낮다. 따라서 면접 순위가 현재까지 합격자 중 가장 높은 값(숫자가 가장 작은 값)보다 더 높을 때만 합격 가능하다. 이렇게 하면 O(N)에 최대 합격자를 결정할 수 있다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day22BOJ1946신입사원 { // 1946 신입사원
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
int N = Integer.parseInt(br.readLine());
int[] cnt = new int[N + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
cnt[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
}
int ans = 1;
int c = cnt[1];
for (int i = 2; i <= N; i++) {
if (c > cnt[i]) {
c = cnt[i];
ans++;
}
}
sb.append(ans).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N) — 서류 순위를 인덱스로 활용하므로 정렬 없이 O(N) 순회
- 공간: O(N) — 면접 순위 배열