[python 백준 1946] 신입 사원

접근 방법

1. 서류 1등과 면접 1등 찾기
2. 서류 1등의 면접 등수보다 높고, 면접 1등의 서류 등수보다 높은 사람의 수 = 선발가능한 인원이라고 생각했다.

실패 코드

import sys

# sys.stdin = open('input.txt', 'r')

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    arr = []
    res = 0
    for j in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))

    # 서류 1등, 면접 1등 찾기
    for a in range(n):
        if arr[a][0] == 1:
            docs_win = a
        if arr[a][1] == 1:
            interview_win = a
    # 서류, 면접 모두 1등인 경우
    if docs_win == interview_win:
        res += 1
        check = 1
    else:
        res += 2
    if (check != 1):
        for k in range(n):
            if arr[docs_win][1] > arr[k][1] and arr[interview_win][0] > arr[k][0]:
                res += 1
    print(res)

반례를 찾아보니
1
6
1 6
5 1
3 4
4 3
2 2
6 5

정답은 (5,1),(2,2),(1,6)으로 3이 나와야하는데 5가 나왔다.

정답 코드

import sys

# 테스트 케이스 수
t = int(sys.stdin.readline())

for i in range(t):
    # 지원자 수
    n = int(sys.stdin.readline())
    arr = []
    res = 1
    for j in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
    arr.sort()

    # 서류 1등
    search_win = arr[0][1]
    for k in range(1, n):
        if arr[k][1] < search_win:
            res += 1
            search_win = arr[k][1]
    print(res)

서류 성적을 기준으로 정렬을 하여 면접 등수만 비교하면 된다.

면접을 잘 본 사람이 있을 경우 그 다음 사람은 최근 합격한 사람보다 면접을 더 잘 봐야한다. (서류 등수 순으로 비교하고 있으니)
ex)
1 6
5 1
3 4
4 3
2 2
6 5

1 6 -> 무조건 합격
2 2 -> 최근 합격한 사람(1 6)와 면접 비교하면 등수가 높음 : 합격
3 4 -> 최근 합격한 사람(2 2)와 면접 비교하면 등수가 낮음 : 불합격
4 3 -> 최근 합격한 사람(2 2)와 면접 비교하면 등수가 낮음 : 불합격
5 1 -> 최근 합격한 사람(2 2)와 면접 비교하면 등수가 높음 : 합격
6 5 -> 최근 합격한 사람(5 1)와 면접 비교하면 등수가 낮음 : 불합격

총 3명이 합격

어우 시간...