[Python] 백준 1946번: 신입사원

풀이 전략은 다음과 같습니다.

문제의 핵심은 "다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. "인데요!

1. 서류심사 순위의 오름차순으로 지원자를 정렬한 다음, 순서대로 지원자의 면접시험 순위를 저장합니다.
2. 일단 서류심사 순위가 1등인 지원자는 뽑히겠죠? cnt = 1에서 시작합니다.
3. i 번째 지원자는 j 번째 ( j > i ) 지원자보다 서류심사 순위가 높은 지원자입니다.
   따라서 만약 j 번째의 면접시험 순위가 i 번째보다 낮다면, j 번째는 i 번째보다 서류와 면접 모두 떨어지는 지원자가 됩니다.
   즉, j 번째의 면접시험 순위가 i < j 인 모든 i에 대해 i 번째보다 높다면 cnt +=1을 해주면 됩니다.
4. cnt를 출력합니다.

방법은 현재까지 가장 높은 순위를 저장할 highest_rank 변수를 이용하는 겁니다.

highest_rank 변수에 가장 높은 순위를 저장한 다음,
highest_rank의 값이 j보다 크면 cnt+=1을 해주면 됩니다.

일단 highest_rank를 서류심사 1위인 지원자의 면접시험 순위로 초기화해줍니다.
이후, 서류심사 2위인 지원자부터 순회하며
지원자의 면점시험 순위가 highest_rank보다 높은지 검사합니다.

만약 지원자의 면접시험 순위가 highest_rank보다 높다면 cnt+=1를 해준 다음
highest_rank의 값을 현재 지원자의 면접시험 순위로 업데이트해주면 됩니다.
(highest_rank에는 현재까지 가장 높은 순위를 저장해야하기 때문입니다. )

import sys
T = int(sys.stdin.readline())
answer = ""

for _ in range(T):
    N = int(sys.stdin.readline())
    person = [0 for i in range(N)]
    cnt = 1

    for i in range(N):
        s1, s2 = sys.stdin.readline().split()
        # 서류심사 순위의 오름차순으로 지원자의 면접시험 순위를 저장
        person[int(s1)-1] = int(s2)

    highest_rank = person[0] # 서류심사 1위인 지원자의 면접시험 순위로 초기화
    for i in range(1, len(person)):
    	# 지원자의 면접시험 순위가 highest_rank보다 높다면
        if highest_rank > person[i]:
            cnt += 1
            highest_rank = person[i]

    answer += str(cnt)+'\n'

print(answer)

highest_rank 변수를 이용하면 시간초과를 내지 않고 문제를 해결할 수 있습니다.

풀이방식을 보면 highest_rank에
i < j 인 i번째 지원자들 중 가장 높은 면접시험 순위를 저장하고 있습니다.

j = 1에서 시작하여 수행 과정에서 highest_rank를 구하고,
구한 highest_rank를 이용하여 문제를 풀어가는 원리인데요!

입력 데이터간의 관계를 고려하지 않고, 수행 과정에서 최댓값(highest_rank)을 선택하는 그리디 알고리즘임을 알 수 있습니다.