백준 1946 파이썬

www.acmicpc.net/problem/1946

1946번: 신입 사원

이 문제는 우선 이해가 중요해 보인다. 처음에 문제 자체를 이해 못 해서 어떻게 접근해야 예제 정답이 나오는지도 긴가민가해서.. 처음에 조금 시도하다가 방치해 두었다가 다시 꺼내서 풀었다.

 

1946 질문에서 어떤 분이 코멘트에 너무 잘 설명해주셔서 설명을 그대로 가져왔다.

 

지원자가 모두 한 장소에 모였다고 생각해 볼게요.
그 중에 한 지원자의 입장이 되어, 다른 지원자들의 면접, 서류 점수를 봅니다.
그 중에 어떤 한 사람이라도 나보다 두 점수가 더 높으면, 나는 선발이 안 됩니다. 그런 사람이 없으면 나는 선발되는 거고요.
이를 모든 지원자에 대해 다 해보는 것입니다.

 

여기서 내가 얻은 힌트는 그럼 우선 list 의 정렬 기능(sort)를 써보면 어떨까? 였다. 

리스트로 정렬해서 한 번 print해보고 결과를 보며 생각해보니,

첫 번째 서류 심사에서 1등을 한 사람은 무조건 선발된다. 서류 심사 2등은 1등의 면접 점수보다 높은 등수를 가지면 선발된다. 

 

라는 결론을 내릴 수 있었다. 

즉, 처음에 정렬을 통해 서류 심사 등수를 일괄적으로 정리하고, 오직 면접 등수로만 선발 유무를 판단하는 것과 같다. 

 

그래서 처음에는 단순하게 for 문을 돌면서 내 서류심사 등수보다 바로 앞에 있는 사람의 면접 등수를 나와 비교하는 식으로 코드를 짰는데, '틀렸습니다'를 받았다. 그래서 반례를 찾다 보니 아하, 내 기준이 잘못되었다는 걸 인지할 수 있었다.

 

단순히 앞사람과 비교하다간 문제가 생기는데, 대표적인 문제는 이와 같다.

 

<입력>

1
7
1 4
2 3
3 2
4 1
5 7
6 6
7 5

<만약 서류 등수 앞 사람과의 비교'만' 진행한다면 결과>

6

<실제 정답>

4

 

왜 그럴까? 바로 5 7/ 6 6 / 7 5 부분에서 문제가 생긴다.

5 7은 자연스럽게 선발되지 못한다. 그런데 6 6 은 앞의 5 7 과 비교했을 때 6이 7보다 작기 때문에 선발된다는 착각을 하게 된다.

 

즉, 앞사람과의 비교가 아니라 '최솟값'으로 비교를 해야 문제 없이 돌아간다. 아까와 같은 상황에서는 4번째 루프인 4 1 에서 1이 최솟값이 되므로 자연스럽게 5 7 /6 6 /7 5는 탈락하게 된다.

 

<전체 코드>

from sys import stdin

a = []
passed = []
t = int(stdin.readline())

for i in range(0, t):
    passed.append(1)
    n = int(stdin.readline())
    for j in range(0,n):
        ranks = list(map(int, stdin.readline().split()))
        a.append(ranks)
    a.sort();
    
    min = a[0][1]

    for j in range(1, n):
        if a[j][1] < min:
            passed[i] += 1
            min = a[j][1]

    del a[0:]

for i in range(0,t):
    print(passed[i])