BOJ 2246 - 콘도 선정

문제

BOJ 2246 - 콘도 선정

N개 콘도의 거리와 비용이 주어질 때, 자신보다 가깝고 저렴한 콘도가 없는 후보의 수를 구하라.

입력

첫째 줄에 콘도 수 N, 이후 N줄에 각 콘도의 거리와 비용이 주어진다.

출력

후보 콘도의 수를 출력한다.

예제

풀이

거리순으로 정렬하면, 자신보다 가까운 콘도는 모두 앞에 위치한다. 따라서 순회하며 최소 비용을 갱신하면 후보를 판별할 수 있다.

1. 콘도를 거리 오름차순으로 정렬한다
2. 현재까지의 최소 비용을 추적하며 순회한다
3. 현재 콘도의 비용이 지금까지의 최소 비용보다 작으면 후보로 카운트하고 최소 비용을 갱신한다
4. 그렇지 않으면 더 가깝고 저렴한 콘도가 있으므로 후보가 아니다

핵심 아이디어: 거리순 정렬 후 최소 비용 갱신 방식으로, 자신보다 가까운 모든 콘도의 비용을 일일이 비교하지 않고 O(N log N)에 해결한다.

코드

import sys
 
input = sys.stdin.readline
A = sorted(tuple(map(int, input().split())) for _ in range(int(input())))
m = 20000
ans = 0
for _, y in A:
    if y < m:
        ans += 1
        m = y
print(ans)

복잡도

• 시간: O(N * log N)
• 공간: O(N)