백준 문제풀이 - 1946 번

링크 -> https://www.acmicpc.net/problem/1946

1. 요약 및 풀이방법

신입 사원 지원자들의 서류, 면접 성적을 기준으로 회사 기준에 맞춰 선발 할 수 있는 최대 인원수를 구하는 프로그램을 작성하는 문제입니다.

신입 사원 선발 기준은 서류와 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 지원자만 선발한다는 원칙입니다.
즉, 어떤 지원자 A의 성적이 다른 지원자 B의 성적에 비해 서류 및 면접 성적이 모두 떨어진다면 A는 결코 선발될 수 없습니다.

지원자를 서류 점수를 기준으로 오름차순 정렬합니다.
그렇게 하면 현재 지원자는 위의 지원자들보다 이미 서류 성적이 부족합니다.
이때, 위의 지원자들 중 한명이라도 현재 지원자보다 면접 성적이 높다면 현재 지원자는 결코 선발될 수 없습니다.

따라서 위의 지원자들의 면접 성적 중 최고 점수를 따로 기억하여
아래로 진행하면서 최고 면접 성적과 비교합니다.
다시 말해 이때 최고 면접 성적보다 면접 성적이 좋지 않으면 결코 선발될 수 없습니다. (이미 서류 성적은 낮기 때문에)

2. Code

import sys

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        rankings = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
        rankings.sort()
        high_rank = rankings[0][1]
        for rank in rankings[1:]:
            if rank[1] > high_rank:
                N -= 1
            high_rank = min(high_rank, rank[1])
        print(N)

if __name__ == "__main__":
    main()

3. 학습 내용

성적 비교를 하며 처음엔 O(N^2)의 시간 복잡도로 문제를 해결하였습니다.
이때 주어진 문제의 시간제한은 2초인데 주어진 N의 범위는 다음과 같습니다.
1 <= N <= 100,000
O(N^2)의 시간 복잡도로는 약 100억으로 시간초과 되었습니다.
따라서 O(N) 의 시간 복잡도로 해결 했습니다.

4. 결과