[Baekjoon, Python] 1946번 : 신입 사원

도입

백준 알고리즘 분류-그리디 알고리즘 열 세 번째 문제이다.

백준 1946번 문제, 입력, 출력

---

백준 1946번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 리스트 안에 리스트를 만든다. 바깥 리스트는 참여자들의 리스트, 안의 리스트는 각 참여자의 서류순위와 면접순위를 나타내는 리스트. 서류순위와 면접순위의 위치(index)는 0, 1로 고정이기 때문에, 상수를 의미하는 DOC_GRD(서류순위) = 0, INV_GRD(면접순위) = 1,로 선언한다.

 

2. 순위를 나타내기 때문에 숫자가 작을 수록 합격에 가까워 진다. 상대와 비교를 해서 내 순위가 더 높다면(숫자가 작다면) 절대 탈락할 일이 없다. 

 

3. 그렇다면, 어떤 것을 기준으로 잡고 어떻게 정렬을 한 뒤 비교를 시작할 것인가? 서류순위? 면접순위? 순위가 높은 순? 순위가 낮은 순? 비교는 어떤 것을 비교할 것인가?

서류 순위든 면접 순위든 상관이 없다. 다만, 정렬로 채택한 순위(서류 or 면접)가 높은 순으로 정렬 하냐, 순위가 낮은 순으로 정렬 하냐에서는 차이가 있다. 높은 순서대로 정렬 후 비교를 하게 되면, 일단 제일 첫 번째 참여자는 무조건 합격이다. 정렬로 택한 순위에서 1등이기 때문에 다른 이들과 비교를 해도 1등 보다 높을 수는 없기 때문이다.

어떤 것을 비교할 것인가? 정렬로 택한 순위(서류 or 면접)의 반대 순위로 비교한다. 정렬한 뒤 1등의 다른 순위를 기준으로 잡고 그 다른 순위들을 비교하고 더 높은 순위가 나타나면 기준을 해당 참여자로 바꿔준다.

---

코드

from sys import stdin

DOC_GRD = 0     # 서류심사 상수
INV_GRD = 1     # 면접심사 상수

var_T = int(stdin.readline())  # 1 <= T <= 20

for _ in range(var_T):
    applicants = []
    available_count = 1
    var_N = int(stdin.readline())  # 1 <= N <= 100,000
    for _ in range(var_N):
        applicant = list(map(int, stdin.readline().split()))
        applicants.append(applicant)

    applicants.sort(key=lambda x : x[DOC_GRD])  # 서류심사 기준으로 정렬, 오름차순
    inv_max = applicants[0][INV_GRD]

    for i in range(var_N):
        if  inv_max > applicants[i][INV_GRD]:
            available_count += 1
            inv_max = applicants[i][INV_GRD]

    print(available_count)

---

마무리

 생각보다 고민이 필요한 문제.