[백준] 1946번: 신입 사원 (Python, 파이썬)

문제 링크: https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

어려웠던 문제!!!

 

(1) 첫 번째 시도

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    scores = [list(map(int, input().split())) for _ in range(n)]
    scores = sorted(scores, key = lambda x: x[0])
    res = 0
    temp = scores[0][1] 
    scores_a = [scores[i] for i in range(n) if scores[i][1] <= temp]

    scores_b = sorted(scores_a, key=lambda x: x[1])
    temp = scores_b[0][0]
    scores_b = [scores_b[i] for i in range(len(scores_b)) if scores_b[i][0]<=temp]
    print(len(scores_b))

 

(2) 두 번째 시도

t = int(input())

for _ in range(t):
    n = int(input())
    scores = []
    res = n
    for _ in range(n):
        a, b = map(int, input().split())
        scores.append([a, b])
        if a == 1:
            x = b
        elif b == 1:
            y = a
    for i, (a, b) in enumerate(scores):
        if a > y or b > x:
            res -= 1
    print(res)

두 케이스 모두 아래 케이스에서 틀린 답을 낸다.

 

정답 코드 (참고)

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    scores = [list(map(int, input().split())) for _ in range(n)]
    scores = sorted(scores)
    
    top = 0
    result = 1
    
    for i in range(1, len(scores)):
        if scores[i][1] < scores[top][1]:
            top = i
            result += 1
    
    print(result)

 

예제 케이스

Key point

(1) 서류 순위 기준으로 오름차순 정렬

(2) 첫 번째 사람은 어차피 서류 1등이므로 일단 합격 (result = 1)

(3) 두 번째 사람부터 면접 순위를 살펴보면서, 첫 번째 사람의 면접 순위보다 낮으면 탈락 (서류 순위는 이미 밀려났으므로, 면접 순위라도 높아야 합격임)

(4) 그 다음 면접 순위가 더 높은 사람 ([4 2])의 면접 순위를 기준으로 설정하고, 또 아래 쭉 살펴봄. 

서류 순위가 낮은 사람들 중에서 합격할 수 있는 사람은 면접 순위가 기준보다 높은 사람만임!

 

첫 번째, 두 번째 시도에 해결하지 못했던 것도 해결!