[Python] 백준 1946번 이해하기

 

 

 

백준 1946번 신입사원 문제 

 

이번 주는 GREEDY 알고리즘을 공부하고 있다. 모르더라도 문제 풀이를 읽으며 이해가 가능했는데 요 문제는 뭔가 문제 자체를 이해하기도 어려웠고 풀이하는 것도 어려웠다. (T_T) 그래서 혹시나 요 문제 이해가 잘 안되는 분들을 위해 풀이를 정리해보고자 한다. 

 

 

백준 1946번 문제 풀이 

 

문제 풀이 : 헷갈렸던 점은 바로 ! 입력되는 저 숫자들은 성적이 아니고 순위입니다. 이 문제를 풀며 다시 한번 문제를 제대로 잘 읽어야하는 중요성을 느꼈습니다. 그 다음 헷갈리는 것은 신입사원으로 뽑는 기준입니다. 기준은 한 지원자의 서류, 면접 성적이 다른 어떠한 지원자보다 최소 1개라도 높으면 채용이 됩니다. 즉, A의 서류순위, 면접 순위가 B 보다 둘 다 낮으면 A는 100% 떨어지고 B는 100% 붙게됩니다. (본인보다 서류, 면접 둘 다 점수가 낮은 다른 지원자가 있으므로) 

 

즉, 탈락하는 지원자는 다른 지원자들 중의 단 한명보다 서류, 면접 두 항목의 점수가 낮으면 (순위가 낮으면) 탈락입니다. 누군가보다 한 항목의 점수가 낮거나 높아서 탈락이 아닙니다. A의 서류항목보다 내 점수가 높아도 B의 서류, 면접 항목 두 점수가 나의 두 점수보다 높은 경우에 내가 탈락하게 됩니다. 

 

 

먼저 정답코드를 보면서 이해해봅시다! 

 

정답 코드 

t = int(input())

for i in range(t):
    n = int(input())
    a = []
    for j in range(n):
        x,y = map(int,input().split())
        a.append([x,y])
    a.sort()

    L = a[0][1]
    index = 1
    for j in range(1,n):
        if a[j][1] < L:
            L = a[j][1]
            index += 1
    print(index)

t = 입력받는 테스트 케이스 

n = 지원자의 수 

 

먼저 지원자들의 순위(x,y) 를 a 라는 리스트에 넣습니다. 그리고 서류 성적 (리스트의 index 0 ) 으로 리스트를 정렬합니다. ----> 이렇게되면 아래처럼 쭉 나열이 되고 ( 동점은 없다는 조건이 있습니다.) 가장 위의 a[0] 의 지원자는 100% 합격하게 됩니다. 첫번째 서류 성적이 1등이기 때문에 면접 점수는 다른 이보다 낮더라도 서류 점수는 1등이므로 100% 합격입니다. 

 

L 이라는 변수에 1등의 두번째 면접 시험 순위를 넣습니다. 그 이유는 1등의 면접 시험보다 더 잘 본 사람들이 합격을 하게 됩니다. (100% 는 아닌 이유는 오른쪽 예시를 보시면 됩니다.) index는 채용이 될 신입사원의 수 입니다. a[0] 지원자는 100% 합격이고 뒤의 for문에서 이 일등 지원자를 굳이 비교하지 안하도 되어서 index = 1로 시작합니다. (여기서 일등을 기준 (L) 으로 놓고 비교하기 때문에) 

 

오른쪽 예시를 보면 1등은 면접 순위가 4등입니다. 그 다음 두번째 지원자는 서류가 2등, 면접이 5등입니다. 서류는 a[0]이 가장 높았고 두번째 지원자는 면접 점수도 L 값 (a[0][1] 1등의 면접순위) 보다 낮습니다. 서류, 면접 둘 다 낮기 때문에 뽑힌 지원자를 넣는 변수 index += 1 조건에 맞지 않으므로 넘어갑니다. 세 번째 지원자도 면접이 6이므로 넘어감니다.

 

이제 네 번째 지원자의 면접 순위는 2입니다. 일 등(4위) 보다 높기 때문에 해당 지원자는 채용이 됩니다. 그렇다고 무조건 일등의 면접 순위로만 나머지 사람들의 합격 불합격 여부를 알 수 있는 것은 아닙니다. 네 번째 지원자가 index += 1이 된 후, 뽑힌 네 번째 지원자의 면접 점수를 L 변수에 넣게 됩니다. 

 

그 이유는 서류는 현재 순차적으로 정렬되어 있고 즉, 뽑힌 사람 뒤에 오는 배열들, 지원자들은 모두 네 번째 지원자의 서류 순위보다 낮습니다. 그럼 이 사람들이 뽑히려면 방금 뽑힌 네 번째 지원자보다 면접 순위가 높아야 그나마 하나라도 점수가 높으므로 채용이 됩니다. 또 누군가 뽑히면 그 사람의 면접 점수를 L에 넣고 for 문이 돌려집니다. 

 

즉, 서류는 어차피 정렬로 정해졌고 앞에사람보다 인터뷰 점수가 더 높으면 뽑힌다. 근데 그 앞에 사람은 L에 index +=1가 된 사람이다! 

 

<첫번째 케이스> <두 번째 케이스>

 

 

정말.. 힘겨운 코테였습니다.. 

 

 

그리고 sys.stdin.readline을 하지않으면 시간 초과가 나니 꼭 sys import 하세요 !! 

모두 코테 화이팅