[그리디 알고리즘] ▲ 1946번 - 신입 사원

[백준] 1946번 - 신입 사원

1) 문제 해결 아이디어

처음에 제출했을 때는 시간초과로 실패했다.

시간 초과가 떴을 때는 input() 대신 sys.stdin.readline() 을 이용한다.

그런데도 시간초과가 떴다.

처음 생각한 방법은 

 

일단 서류 순위 기준으로 오름 차순 정렬한다. (동석차는 없으므로 서류 기준으로만 정렬해도 된다.)

서류, 면접 둘 중 1개라도 1위인 지원자는 무조건 뽑힌다. 

오름차순 정렬해놓았으므로 0번째 인덱스인 지원자는 자동 선발 처리하여 선발 인원 수(cnt)를 1로, 최고 면접 순위(high_rank)를 0번째 인덱스 지원자의 면접 순위로 초기화한다.  다음 인덱스인 1 ~ (n - 1)번째 리스트를 대상으로 for문을 돌린다.

 

선발이 되면 선발 인원수(cnt)를 변경하고 면접 최고 순위(high_rank)를 갱신한다.

면접 순위가 1이면 추가적인 검사를 하지 않고 바로 선발한다. 

현재 지원자의 면접 순위는 지금까지 지원자의 면접 최고 순위보다 높을 경우에만 선발된다.

 

[참고] https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%801946%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%8B%A0%EC%9E%85-%EC%82%AC%EC%9B%90

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

 

2) 소스코드

import sys

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

for _ in range(t):
  n = int(input())  # 지원자 수
  # n개의 지원자 서류, 면접 순위(2차원 리스트)
  arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

  # 오름차순 정렬(서류 기준)
  arr.sort(key = lambda x : x[0])

  cnt = 1  # 선발 인원 수
  high_rank = arr[0][1]  # 면접 최고 순위
  for i in range(1, n):
    rank = arr[i][1]  # 현재 면접 순위
    # 면접 순위 1위이면 선발
    if(rank == 1):
      cnt += 1
      high_rank = rank  # 높은 랭크 갱신
      continue
    # 현재 면접 순위가 면접 최고 순위보다 높으면
    if(rank < high_rank):
      cnt += 1
      high_rank = rank  # 높은 랭크 갱신    
  print(cnt)​

<빠른 입력받기>

sys.stdin.readline()

​input() 과 동일