[복기] 1946번: 신입 사원

문제

1946번: 신입 사원

알고리즘 분류

• 그리디 알고리즘
• 정렬

나의 풀이 1(실패)

우선 문제를 제대로 이해를 못해서 좀 헤맸었다. "다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다"를 "하나라도 떨어지면 떨어뜨린다"로 이해해서 예제 케이스를 이해하지 못했다. "어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다"는 조건을 제대로 이해하면 된다.

나의 풀이과정은 단순하다. 서류심사와 면접시험에서 각각 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.sort(key=lambda x: x[0])
    first = scores[0]
    scores.sort(key=lambda x: x[1])
    second = scores[0]
    
    answer = 0
    for i in range(n):
        if scores[i][1] <= first[1] and scores[i][0] <= second[0]:
            answer += 1
    
    print(answer)

솔루션

신입사원 풀이

솔루션의 로직은 엄청 단순하다. scores를 정렬하면 어차피 서류심사 성적에 대해서는 오름차순으로 정렬되기 때문에 볼 필요가 없다. 이제 면접시험 성적에 대해 낮은 값(성적 높은 지원자)을 갱신해가면서 합격시킨다. 서류심사 성적이 높은 순서대로 보기 때문에 어차피 뒷사람은 서류심사 성적은 낮을 수 밖에 없다. 따라서 합격하기 위해서는 면접시험 성적이 현재 지원자보다 높은 사람이어야 한다.

로직이 상상 이상으로 단순해서 놀랐다. 허탈하기도 하다.

전체 코드

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.sort()
    
    answer = 1
    winner = scores[0][1]
    for i in range(1, n):
        if winner > scores[i][1]:
            winner = scores[i][1]
            answer += 1
    print(answer)