[Python] 백준(BOJ): 1946 신입사원

문제

1946번: 신입 사원

---

풀이

a. 시간 초과

서류순위를 기준으로 오름차순 정렬을 수행한다
서류 순위가 1등인 이는 무조건 채용이 될 것이므로, [1: 지원자수]의 범위에 대하여 합격 여부를 확인한다
지원자보다 서류 순위가 높은 모든 이에 대하여, 면접 순위를 비교한다
서류/면접 순위가 모두 떨어지는 이를 합격자 명수에서 제외한다

해당 풀이의 경우 O(N^2)의 시간복잡도를 가지게 된다. 시간 초과로 실패

import sys
T = int(input())

for t in range(T):
    n = int(input())
    data = []
    for i in range(n):
        data.append([j for j in map(int, sys.stdin.readline().split())])
    data.sort()

    answer = n
    for i in range(1, n):
        interview = data[i][1]
        for j in reversed(range(i)):
            if data[j][1] < interview:
                answer -= 1
                break

    print(answer)

 

b.  풀이

서류 1등의 면접 순위로 기준값을 설정하고, 면접 순위를 비교하게 코드를 수정하였다

• 서류/면접 순위가 모두 떨어지는 지원자가 발생할 경우, 합격자에서 제외한다
• 기준을 통과한 경우(서류/면접 중 적어도 하나가 다른 지원자보다 우위에 있는 경우), 면접 기준 순위를 갱신한다

import sys
T = int(input())

for t in range(T):
    n = int(input())
    data = []
    for i in range(n):
        data.append([j for j in map(int, sys.stdin.readline().split())])
    # 서류 순위를 기준으로 오름차순 정렬
    data.sort()

    answer = n
    # 면접 순위 기준값 설정
    standard = data[0][1]
    
    # 면접 순위 기준을 만족하는지 확인
    for i in range(1, n):
        # 만족하지 않는 경우 (서류/면접 순위가 모두 다른 지원자보다 떨어지는 경우), 합격자에서 제외
        if standard < data[i][1]:
            answer -= 1
        # 만족하는 경우, 면접 순위 기준값을 업데이트
        else:
            standard = data[i][1]
    print(answer)

 

불합격자를 제하는 것이 아닌, 합격자의 수를 ++하는 방향으로도 코드를 작성해보았다

import sys
T = int(input())

for t in range(T):
    n = int(input())
    data = []
    for i in range(n):
        data.append([j for j in map(int, sys.stdin.readline().split())])
    data.sort()

    answer = 1
    standard = data[0][1]
    for i in range(1, n):
        if standard > data[i][1]:
            answer += 1
            standard = data[i][1]

    print(answer)