https://www.acmicpc.net/problem/1946

1차 시도

import sys
input = sys.stdin.readline

t = int(input())
for case in range(t):
    candidates = []
    c = int(input())
    answer = [1] * c
    for _ in range(c):
        candidates.append(list(map(int, input().split())))

    for i in range(c):
        for j in range(c):
            s1 = candidates[i]
            s2 = candidates[j]
            if s1[0]>s2[0] and s1[1]>s2[1]:
                answer[i] = 0
    print(sum(answer))

• 당연히 시간초과한 O(N^2)

통과한 코드

import sys
input = sys.stdin.readline

t = int(input())
for case in range(t):
    candidates = []
    c = int(input())
    answer = [1] * c
    for _ in range(c):
        candidates.append(list(map(int, input().split())))
    candidates.sort()       # 서류 순위 높은 순으로 정렬
    # 앞 쪽에 있는 사람보다 서류 전형의 등수가 높을 수 없기 때문에 면접 등수는 앞의 사람보다 높아야 함
    cutline = candidates[0][1]
    for i in range(c):
        s1, s2 = candidates[i]
        if s2 > cutline:
            answer[i] = 0
        cutline = min(cutline, s2)
    print(sum(answer))

• for 문 하나를 어떻게 줄일지 생각하기

• 서류 전형의 등수를 기준으로 정렬하여 앞 사람의 서류 전형 등수는 고려하지 않음
• 뒷 사람은 앞 사람보다 무조건 서류전형 등수가 낮으므로 앞사람까지의 면접 전형 등수보다 높으면 합격 --> min(cutline, s2)