백준(Baekjoon Online Judge) - 1946번(신입 사원) 문제 풀이

1. 문제

2. 입출력 예시

3. 문제 풀이

이 문제는 어찌보면 매우 간단하게 해결가능하나, 시간초과를 고려해야 하기 때문에 골치아픈 문제이다. 이 문제 흐름의 핵심은 정렬 후 값의 크기 비교이다. 서류심사 순위와 면접심사 순위가 주어지는데, 다른 사람들과 비교하였을 때 두 개 순위 모두 뒤처질 경우 탈락하는 방식이다. 즉, 둘 중 하나는 다른 사람들보다 높아야하므로 이를 알아보기 쉽게 서류심사 순위를 기준으로 오름차순 정렬을 해주어야 한다.

주어진 예시를 통해서 확인해보자. 먼저 5명인 경우 [(3, 2), (1, 4), (4, 1), (2, 3), (5, 5)]가 주어진다. 이를 서류심사 순위를 기준으로 오름차순 정렬을 해보면 [(1, 4), (2, 3), (3, 2), (4, 1), (5, 5)]이며, 표로 나타내보면 아래와 같다.

위 예시는 매우 간단하게 나와있기 때문에 누가 탈락할 것인지(5, 5)를 한 눈에 알아볼 수 있다. 주어진 예시 중 7명인 경우의 예시를 통해 자세히 알아보도록 하자. 이 경우도 마찬가지로 서류심사 순위를 기준으로 오름차순 정렬을 하면 아래 표와 같다.

위의 표를 통해 면접심사 순위를 비교하면 아래와 같은 결과를 확인할 수 있다. 서류심사 순위의 경우 오름차순 정렬을 해주었기 때문에 이전 순서의 사람과 비교하였을 때 낮을 수 밖에 없으며, 면접심사 순위는 비교했던 사람들 중 가장 높은 순위를 기준으로 계속해서 비교해야 한다.

이러한 논리를 수행하기 위하여 순서를 세워보았다.

• 테스트 케이스의 수량(T)을 입력 받으며, T 만큼 반복하는 동안 아래의 동작을 수행한다.
  • 지원자의 수(N)를 입력 받으며, 지원자의 수 길이 만큼 숫자 0을 요소로 지닌 리스트(P)를 생성한다.
  • 지원자의 수 만큼 지원자의 면접심사 순위와 서류심사 순위를 입력받으며, 입력 받은 문자열은 공백을 기준으로 나누어 준다.
  • 서류심사 순위(x)를 기준으로 오름차순 정렬과 동시에 면접심사 순위(y)를 별도로 추출하기 위하여 P[x - 1] 를 면접심사 순위로 변경한다.
  • 첫 번째를 제외한 모든 사람들의 면접심사 순위가 이전 사람의 면접심사 순위보다 낮아야 합격하므로 최상위 면접심사 순위(MIN)를 첫 번째 사람의 면접심사 순위로 초기화하며, 첫 번째 사람은 무조건 합격이므로 합격자 수(CNT)를 1로 초기화한다.
  • 첫 번째 사람을 제외한 나머지 모든 사람의 수 만큼 반복하며, 해당 사람의 면접심사 순위(p)가 최상위 면접심사 순위(MIN) 보다 높을 경우(p < MIN) 합격자 수를 증가(CNT += 1) 시키고, 최상위 면점심사 순위(MIN)를 해당 사람의 면접심사 순위(p)로 초기화한다.
  • 반복이 끝나면 합격자 수(CNT)를 출력 후 테스트케이스 수량 만큼 이를 다시 반복한다.
• 테스트 케이스 수량 만큼의 반복이 끝나면 프로그램을 종료한다.

이를 코드로 나타내면 아래와 같다.

T = int(input())

for _ in range(T):

    N = int(input())
    P = [0 for _ in range(N)]

    for i in range(N):
        x, y = map(int, input().split())
        P[x-1] = y

    MIN = P[0]
    CNT = 1

    for p in P[1:]:
        if p < MIN:
            CNT += 1
            MIN = p

    print(CNT)

그러나, 위의 코드를 제출하면 시간초과라는 결과를 받게 된다. 이를 해결하기 위하여 pop, queue 등을 사용하였음에도 불구하고 결과는 동일했다. 다른 사람들이 작성해놓은 코드를 통해 내가 작성한 코드를 검토하던 중 새로운 입력 방식에 대해 알게 되었다. 기존에 내가 알던 입력 방식은 input()이 전부였으나, 새로 알게된 방식은 sys.stdin.readline()이며, 수정한 코드는 아래와 같다.

import sys


T = int(sys.stdin.readline())

for _ in range(T):

    N = int(sys.stdin.readline())
    P = [0 for _ in range(N)]

    for i in range(N):
        x, y = map(int, sys.stdin.readline().split())
        P[x-1] = y

    MIN = P[0]
    CNT = 1

    for p in P[1:]:
        if p < MIN:
            CNT += 1
            MIN = p

    print(CNT)

위의 코드로 수정 후 다시 제출하였더니 맞았습니다라는 결과를 받았으며, 메모리 33,412 KB, 시간 2,496 ms가 소요되었다. input()과 sys.stdin.readline()은 각각 어떠한 방식으로 동작하길래 구현 시간에 있어서 시간 차이가 발생하는걸까? 이 궁금증은 조금 더 검색 후 공부한 다음에 정리하여 포스팅하도록 하겠다.

참고자료

• 백준알고리즘 문제 - 1946번 신입 사원