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

문제

1946번: 신입 사원

- 신규 사원 채용은 1차 서류심사, 2차 면접시험으로 이루어져 있다.

- 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른   지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.

- 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

- 위 조건을 만족시키면서, 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 문제이다.

- 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다.

- 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다.

- N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다.

- 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

알고리즘

- 테스트 케이스의 개수를 입력받는다.

- 테스트의 케이스만큼 반복하여 지원자의 수와 지원자의 성적을 입력받는다.

- 지원자의 성적은 서류심사 성적기준으로 정렬한다.

- 이때, 첫 번째로 오는 지원자는 다른 지원자보다 서류심사 성적이 높기 때문에 합격이 된다.

- 합격된 지원자의 면접시험 성적기준으로 다른 지원자의 면접시험 성적을 비교하여 그보다 높은 지원자를    합격시킨다.

코드

import sys

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

# 테스트 케이스 만큼 반복한다.
for _ in range(test_case):
    # 지원자의 수를 입력받는다.
    n = int(sys.stdin.readline())
    # 서류심사 성적과 면접시험 성적을 입력받아 서류심사 성적기준으로 정렬한다.
    test = sorted([list(map(int, sys.stdin.readline().strip().split())) for x in range(n)],
                  key=lambda x: x[0])
    # 서류심사 성적기준, 오름차순으로 정렬했기 때문에 test[0]번째 지원자는 합격이다.
    count = 1
    # 합격한 지원자 면접시험 성적 기준으로 비교한다. 
    target = test[0][1]

    for i in range(1, n):
        # 합격한 지원자보다 면접시험 성적이 높으면 합격
        if test[i][1] < target:
            # 합격한 지원자에 면접시험 성적으로 바꿔준다.
            target = test[i][1]
            # 합격한 지원자 카운트
            count += 1

    print(count)

결과

위 코드에서 처음 반복문에 print(test)를 작성하면 서류심사 성적기준으로 정렬된 지원자의 성적들을 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 첫 번째 케이스에서 서류성적 심사기준, 오름차순으로 정렬된 것을 볼 수 있다. 이렇게 서류성적 심사기준으로 정렬하게 되면 면접시험 성적기준으로만 비교하여 합격시킬 수 있다. 이때, 서류심사 성적이 1등인 지원자는 다른 지원자보다 서류심사 성적이 높기 때문 자동으로 합격이 된다. 다음으로 서류심사 성적 등수대로 합격한 지원자보다 면접시험 성적이 더 높으면 합격시키면 된다. 

github

junjange/CodingTest