악곱 == 악성곱슬

그리디

---

해당 문제를 그리디 유형으로 접근 한 정당성은 다음과 같다.

• 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발 → 정렬을 통해 접근할 수 있겠다 → 한 종목에 대해 정렬을 한 후 완전탐색하여 순간의 최소 순위를 통해 고를 수 있겠다

시간복잡도

• test case T가 최대 20, input의 사이즈가 최대 10만 → 10만의 N^2은 100억이다. 시간초과가 날 수밖에 없음
• 따라서 NlogN의 알고리즘까지 사용할 수 있겠다. → Python의 sort 메서드는 NlogN을 지원하므로 이를 이용해서 구현해보자

위와 같은 생각을 통해 구현한 코드는 아래와 같다.

import sys

def solution(ranks, n):
    answer = 1
    # 한 종목을 오름차순으로 정렬
    ranks.sort(key=lambda x: x[0])  # O(NlogN)
    rank_min = ranks[0][1]
    # 나머지 한 종목을 순회하며 검사 O(N)
    for rank in ranks:
        if rank[1] < rank_min:
            rank_min = rank[1]
            answer += 1
    return answer

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    # solution 제외 O(TN) -> 약 200만
    # solution O(NlogN) -> 약 50만
    # 도합 O(TNlogN) -> 약 1000만
    # 제한시간이 2초 이므로 약 2000만번의 수행 이내에 끝내야 한다.
    for _ in range(T):
        test_ranks = list()
        N = int(sys.stdin.readline().rstrip())
        for _ in range(N):
            doc, interview = map(int, sys.stdin.readline().rstrip().split())
            test_ranks.append([doc, interview])

        print(solution(test_ranks, N))