[알고리즘/그리디] 1946 번 : 신입 사원 - python

링크 : https://www.acmicpc.net/problem/1946

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법) 

1. 테스트 케이스 입력받기, 지원자 수 입력받기, 지원자 리스트 입력받기

2. 알고리즘 생각하기

먼저 서류를 기준으로 오름차순 정렬한다. 그러면

1 5

2 4

3 2

4 1

5 3 과 같은 형태로 나올 것이다.

알고리즘의 핵심은, "뽑힌 사람은 그 누구보다도 서류성적과 면접성적 모두 모자라서는 안된다이다.

즉 이 정렬된 리스트에선 위에서 아래로 갈수록, 무조건 서류성적은 윗사람보다 낮으니 앞선 사람들의 면접성적보다는 높아야 선발조건에 들어간다는 것이다

첫 사람의 면접 성적을 min값으로 잡고, 그 다음사람이 min값보다 면접성적이 높다면(즉, 숫자가 더 작다면) count +=1을 하고 min값을 다음사람의 값으로 대체해준다.

아니라면 그냥 탈락시키면 된다

3. 결과를 출력한다

 

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

t = int(input())  # 테스트 케이스

for _ in range(t):
    new = int(input())  # 신입사원 수
    new_list = []  # 신입사원 리스트
    for _ in range(new):
        new_list.append(list(map(int, input().split())))  # 각자의 서류 성적과 면접 성적 입력
    count = 1
    new_list.sort(key=lambda x: x[0])  # 서류 성적 순위로 정렬
    min_grade = new_list[0][1]  # 4 면접 성적 최소 기준
    for i in range(len(new_list)):
        if min_grade > new_list[i][1]:  # 현재 면접최소성적보다 x높은성적(작은 숫자)가 나온다면
            min_grade = new_list[i][1]
            count += 1
    print(count)

---

• 얻어갈 부분

1. 그리디 알고리즘을 판단할 때 알고리즘을 잘못 판단하면 어떤 심각한 반례가 생기는지 알게되었다

2. 알고리즘을 떠올릴때 논리적 공백이 없는지 반례를 조금 더 생각해보자

3. key lambda 메서드에 대해서 익숙해졌다.