[99클럽 5기] 코딩테스트 스터디 19일차 TIL - 그리디 알고리즘

[Silver I] 신입 사원 - 1946 

[문제 링크](https://www.acmicpc.net/problem/1946)

🗝️오늘의 학습 키워드 (Keyword)

• 그리디 알고리즘
• 정렬

---

💻본인의 언어로 내용 정리 (Today I Learned)

신입 지원자들의 서류 심사 성적과 면접 결과 등수가 주어진다. 한 지원자에 대해 다른 지원자보다 두 개의 성적 중 하나라도 높으면 신입 사원으로 선발이 된다.

 

즉 두 개의 성적 모두가 어느 다른 한명의 지원자보다 낮을 경우, 결코 선발이 되지 않는다고 한다.

 

문제를 일부러 꼬아 낸 건지는 모르겠지만, 약간에 함정이 있다.

지원자들의 성적은 다음과 같이 주어진다.

[서류 심사 성적, 면접 결과 등수]

서류 심사 성적은 높은 것이 좋고, 면접 결과 등수는 (숫자가) 낮은 것이 좋은 것이다.

 

따라서 이 문제는 두 개의 성적 중 어느것을 기준으로 문제를 해결해 나갈지를 먼저 선정하는 것이 핵심이다.

 

두 개의 성적 중 하나를 기준으로 정렬을 진행하여 다른 하나의 성적을 비교하는 방식으로 접근해보았다.

 

💡알고리즘 풀이

N = int(input())

people = []
for _ in range(N):
    a, b = map(int, input().split())
    people.append((a, b))
    
people.sort(key = lambda x : x[0]) # 서류 성적이 낮은 순 정렬

지원자 수를 입력 받고, 지원자들의 성적들을 입력 받아 리스트에 저장한다.

이를 key = lambda를 이용하여 서류 심사 성적이 낮은 순으로 정렬한다.

 

pass_num = 1 # 통과한 사람 수
target = people[0][1] # 서류 성적이 젤 낮은 사람의 면접 등수
    
# 등수 비교
for i in range(1, len(people)):
    if (target > people[i][1]): # 등수가 더 크다 -> 순위가 낮다 -> 서류 성적도 낮고 면접 순위도 낮다
        pass_num += 1 # 합격자 한명 추가
        target = people[i][1] # 타겟 변경

print(pass_num)

pass_num : target을 기준으로, target보다 등수가 높은 사람이 있으면 1씩 증가, 등수가 높은 사람이 없을 경우 target이 합격하기에 기본값 1

target : 정렬 후를 기준으로, 성적이 가장 낮은 사람의 등수.

 

서류 심사 성적이 가장 낮은 사람을 target으로 선정, 바로 다음 사람과 등수를 비교하며 합격자를 가린다. 등수(숫자)가 낮다는 것은 더 높은 등수라는 뜻.

 

target을 바꿔 추가 탐색을 진행한다.

 

🗒️제출 코드

# 1946 신입 사원

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())

    people = []
    for _ in range(N):
        a, b = map(int, input().split())
        people.append((a, b))
    
    people.sort(key = lambda x : x[0]) # 서류 성적이 낮은 순 정렬

    pass_num = 1 # 통과한 사람 수
    target = people[0][1] # 서류 성적이 젤 낮은 사람의 면접 등수
    
    # 등수 비교
    for i in range(1, len(people)):
        if (target > people[i][1]): # 등수가 더 크다 -> 순위가 낮다 -> 서류 성적도 낮고 면접 순위도 낮다
            pass_num += 1 # 합격자 한명 추가
            target = people[i][1] # 타겟 변경

    print(pass_num)

---

💭오늘의 회고

문제가 참 까다로웠다. 말 장난 치는건가 싶었다..

 

문제를 대충 읽고 문제를 접근하였다면 아마 수많은 실패가 나왔을 것이다.

테스트 케이스도 이해가 안되어 몇 번이고 검증하였던 문제였다.

 

문제 자체는 크게 어려울 것 없었으나, 역시 등수를 판별하는 과정에서 약간의 혼돈이 생겼다. (숫자가 작아야 더 큰거라니..)

---

⬇️전체 소스코드⬇️

hanghae99/python_middler/19일차 신입 사원/신입 사원.py at main · Do-heewan/hanghae99