문제 설명
서류 심사와 면접 시험을 기준으로 신입 사원을 선발하려고 한다.
지원자는 (서류 심사 성적, 면접 시험 성적) 두 가지 기준으로 평가되며, 두 성적 중 하나라도 다른 지원자보다 떨어지지 않는 경우에만 선발된다.
즉, 어떤 지원자 A가 지원자 B보다 두 성적 모두 낮으면 A는 선발되지 않는다.
이때, 선발할 수 있는 최대 지원자 수를 구하는 프로그램을 작성하라.
입력
- 첫 번째 줄에 테스트 케이스 개수
T가 주어진다. - 각 테스트 케이스의 첫 줄에는 지원자의 수
N (1 \leq N \leq 100000)이 주어진다. - 다음
N개의 줄에 각 지원자의(서류 심사 성적, 면접 시험 성적)이 주어진다. (1등이 가장 높은 순위)
출력
각 테스트 케이스마다 선발할 수 있는 최대 지원자 수를 출력한다.
접근 방법
1. 내가 처음 접근한 방법
처음에는 이중 반복문을 사용하여 모든 지원자들의 서류 및 면접 성적을 비교하면서 선발 여부를 결정하려 했다.
즉, 각 지원자를 기준으로 나머지 지원자들과 비교하여, 자신보다 두 성적 모두 낮은 지원자가 존재하는지 확인하는 방식이었다.
T = int(input())
res = []
for _ in range(T):
N = int(input())
a = []
cnt = N
for i in range(N):
a.append(tuple(map(int, input().split())))
a.sort(key=lambda x: -x[0]) # 서류 성적 기준 내림차순 정렬
for i in range(N-1):
for j in range(i+1, N):
if a[i][1] > a[j][1]: # 면접 성적도 낮으면 탈락
cnt -= 1
break
res.append(cnt)
for i in res:
print(i)🔹 문제점
- 이중 반복문을 사용했기 때문에
O(N^2)의 시간 복잡도가 발생함. N의 최대값이100,000이므로, 최악의 경우100,000^2 = 10^10연산이 발생하여 시간 초과가 발생함.
2. 개선된 방법
시간 초과를 해결하기 위해 이중 반복문을 제거하고, 한 번의 순회로 해결할 방법을 고민했다.
🔹 핵심 아이디어
- 서류 심사 성적을 기준으로 오름차순 정렬하면, 이후 면접 성적만 비교하면 된다.
- 즉, 서류 성적이 높은 순서대로만 면접 성적을 고려하면 됨 →
O(N log N) + O(N) = O(N log N)로 해결 가능!
🔹 깨달은 점
- 서류 심사 성적을 기준으로 오름차순 정렬하면, 이후 면접 성적 비교만 수행하면 됨.
- 서류 심사가 오름차순으로 정렬되어 있으니, 면접 심사일 때는 현재까지 확인한 면접 심사 순위의 최솟값을 갱신하면서 비교하면, 이중 반복문 없이 해결할 수 있음!
개선된 코드
import sys
input = sys.stdin.readline
T = int(input())
res = []
for _ in range(T):
N = int(input())
a = []
for i in range(N):
a.append(tuple(map(int, input().split())))
a.sort() # 서류 성적 기준 오름차순 정렬
cnt = 1 # 첫 번째 지원자는 무조건 선발
min_interview = a[0][1]
for i in range(1, N):
if a[i][1] < min_interview: # 면접 성적이 현재까지의 최소보다 낮으면 선발 가능
min_interview = a[i][1]
cnt += 1
res.append(cnt)
print("\n".join(map(str, res)))시간 복잡도 분석
| 접근 방식 | 시간 복잡도 | 이유 |
|---|---|---|
| 기존 코드 | O(N^2) | 모든 지원자를 비교 |
| 개선된 코드 | O(N log N) | 정렬 + 1회 순회 |
- 기존 코드에서는 모든 지원자를 비교하므로
O(N^2)의 시간 복잡도가 발생했음. - 개선된 코드에서는 정렬 후 1회 순회하여
O(N log N) + O(N) = O(N log N)으로 줄어듦!
✨ 핵심 정리
- 처음에는 이중 반복문을 사용하여 모든 지원자를 비교하려 했으나,
O(N^2)로 인해 시간 초과가 발생함. - 서류 심사 성적을 기준으로 정렬하면 면접 심사만 고려하면 됨을 깨닫고 접근 방식을 변경함.
- 현재까지의 면접 심사 최솟값을 갱신하면서 한 번만 순회하면
O(N log N)으로 해결 가능함! - 이중 반복문 없이 문제를 해결하는 방법을 고민하는 것이 중요! 🚀
꾸준함을 잃지 말자.