[백준] 1946번 신입 사원 파이썬(Python) 풀이

1946번: 신입 사원

[문제]

---

[코드]

import sys
input = sys.stdin.readline

case = int(input())

for _ in range(case):
    N = int(input())
    total = []
    for _ in range(N):
        a, b = map(int, input().split())
        total.append((a, b))

    total.sort(key=lambda x: x[0])
    cnt = 1
    check = total[0][1]
    for i in range(1, N):
        if total[i][1] < check:
            check = total[i][1]
            cnt += 1
    print(cnt)

---

[해설]

그리디 & 정렬 문제이다

오랜만에 정렬 문제를 풀어보려다가 

정렬맛 그리디 문제를 푼것 같다

풀이는 간단하다

 

import sys
input = sys.stdin.readline

case = int(input())

for _ in range(case):
    N = int(input())
    total = []
    for _ in range(N):
        a, b = map(int, input().split())
        total.append((a, b))

 

 

문제 갯수를 Case 변수로 받고 Case 만큼 for 문을 반복해준다

for 문안에서는 신입사원 지원 수N을 input으로 받고 N만큼 for 문을 반복하여 (서류:a, 면접:b)점수를 total 리스트에 추가한다.

 

	 total.sort(key=lambda x: x[0])

그리고 서류를 기준으로 total을 정렬한다 (물론 면접을 기준으로 하고 밑에 부분을 수정해도 상관없다)

 

문제의 핵심은 같은 등수는 없다는 것

즉, 누군가는 반드시 누구 보다 앞선다 

    cnt = 1
    check = total[0][1]
    for i in range(1, N):
        if total[i][1] < check:
            check = total[i][1]
            cnt += 1
    print(cnt)

 

현재, 서류 점수로 정렬 되었다면 맨앞에 있는 사람은 무조건 뽑힐 것이다 (서류 등수가 제일 높기 때문이다)

따라서 우리는 벌써 한명을 뽑았다!!

그러므로 우리가 출력할 최종 결과 cnt = 1로 지정해준다

 

이제 우리가 체크할 것은 서류등수는 이미 정렬 되어 있으니 면접 점수있다

즉, 현재 순서에서 서류등수는 순서대로 되어 있다 

따라서 우리는 면접 점수가 앞에 사람보다 등수가 낮은 사람이 있다면 이 사람은 아쉽지만 채용하지 않으면 된다(슬픈현실)

 

따라서 우리는 check 라는 변수를 통해서 면접 점수의 기준점을 정해준다 -> 당연히 처음은 total[0][1]이다 (참고로 이양반은 채용되었다)

그리고 for 문을 돌면서 total[i][1]이 체크보다 낮은 (즉, 등수가 앞서는) 사람을 찾아준다 

만약 있다면 기준점 check를 그 사람의 면접 점수로 갱신하고 (서류 점수는 어차피 for 문 뒤에 오는 사람은 상대적으로 아래에 있기 때문이다) 최종 결과에 +1를 해준다

 

그렇게 되면 우리가 원하는 최대로 채용가능한 사람을 구할 수 있다

 

 

---

문제의 핵심 :

 1. 정렬 기준 (사실 상관 없다)

 2. 정렬 기준에 따른 기준점 설정 및 갱신하는 그리디 알고리즘 생성

 

문제의 어려운점:

실버1에 해당하는 조금은 수준있는 문제이지만 

다른 실버1 문제에 비하면 어렵지 않은 문제이다 

이 문제를 해결 하기위해서 로직을 생각해는 것이 중요하다 

사실상 이 문제에서 정렬은 그다지 중요한 부분이 아니다. (정렬 기준을 어디에 두는 지는 중요하지 않다 , 서류 or 면접 둘중 하나만 선택하면되는 '선택'의 문제이다 -> 물론 선택으로 인해서 아래 코드가 조금은 수정될 수 있다)

 

결국 문제의 핵심은 '그리디 알고리즘'을 생각해 내는 것이었다 

면접 등수가 높은 사람을 찾으면서 찾을 때 마다 기준점을 그 사람으로 변경시키고 

최종 결과에 +1을 해주는 그리드를 생각해내는 방법 말이다