[알고리즘] BOJ 1946번 - 신입 사원(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy 50문제 풀기

2 / 50(NEW!)

 

탐색 50문제 풀기

1 / 50

 

기초 동적 프로그래밍 50문제 풀기

1 / 50

 

투포인터 10문제 풀기

0 / 10

---

문제

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

1946번: 신입 사원

---

문제 해결 아이디어

아이디어.txt

A 지원자의 서류 심사 결과와 면접 성적이 다른 지원자보다 떨어지는지 판단

=> 이중 for문으로 현재 A에 대해 다른 지원자 중 떨어지는 사람이 있는지 판단 가능,

그러나 지원자의 수가 최대 100,000이므로 불가능

=> 그리디로 최적의 알고리즘을 생각해야 함.

 

지원자를 서류 심사 성적과 면접 성적으로 우선 sort.

만약 문제 예시처럼 성적이 (3, 2), (1, 4), (4, 1), (2, 3), (5, 5)라고 했을 때

sort 결과는  (5, 5) - (4, 1) - (3, 2) - (2, 3) - (1, 4)

마지막 사람은 제외하고(어차피 통과) 앞에서부터 n - 1까지 확인

면접 성적이 뒤 사람보다 낮으면 불통, 아니면 통과

 

최종 아이디어.txt

맞는 줄 알았는데.. 안되서 예외 케이스 생각

한 명이 다 1등 먹은 경우에는 => 다 탈락해서 1명만 살아남음..

내가 짠 알고리즘 대로 하면 X

 

5명이고 다음처럼 입력이 들어오는 경우

1 1
2 3
3 2
4 5
5 4
1인데 3이 되버림..

 

서류 순위와 면접 순위가 같을 때는 그보다 낮은 순위 사람은 모두 불통

==> 만약 같으면 초기화하는 걸 추가

==> 단지 같을 때만 문제가 아니었음을..

 

 

진짜 최종 아이디어.txt

오름차순으로 정렬하고, 앞에서 가장 면접 순위가 높았던 사람과 비교해서 결정

입력이 (4, 5) - (5, 4) - (3, 2) - (2, 3) 일때

5 4 - 4 5 - 3 2 - 2 3

이렇게 했으 때에도 사실 5 4와 4 5는 바로 탈락임 2명만 통과한다.

차라리 오름차순으로 sort를 하고나서

만약 min 보다 크면 탈락 -> 이 때는 업데이트 안 함

그 외에는 합격하고 min 업데이트

---

구현

내 풀이

import sys
input = sys.stdin.readline 

for _ in range(int(input())):
  # 지원자 초기화
  applicants = []
  
  for _ in range(int(input())) : 
    a, b = map(int, input().split())
    applicants.append((a, b))
    
  applicants.sort() # 오름차순으로 정렬
  
  # 합격자, 가장 첫 번째 사람은 무조건 통과
  passer = 1
  # 앞 합격자 중에서 가장 높은 면접 순위
  min_b = applicants[0][1]
  # 마지막 사람 제외 합격 결정
  for idx, (a, b) in enumerate(applicants[1:]) :
    # 면접 순위가 앞 사람들보다 높으면 통과
    if (min_b > b) :
        passer += 1
    min_b = min(min_b, b)
  
  print(passer)

 

---

메모

• 소요 시간: 1시간 18분
• python 문법
  • 두 가지 이상의 조건으로 sort 하기
    • sorted(e, key = lambda x : (x[0], x[1]))

---

마치며

저번에 스무스해서 50문제는 너무 많은가...? 했다가 

아님을 깨달았다 조용히 50문제 풀어야지