[백준] 1946번 신입 사원 - 파이썬

1946번: 신입 사원

 

문제 접근 방법

문제에서 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발 이라는 의미가 헷갈렸다.

깊게 생각해보니 이 말은 서류에서 나보다 점수가 높은 사람들 중에 나의 면접 점수가 가장 높아야한다!

즉, 나보다 국어 점수가 높은 애들과 비교했을 때 수학 점수가 Top이면 된다.

 

제출코드

import sys
input=sys.stdin.readline

T = int(input())
for _ in range(T):
  N = int(input())
  cnt = 1  #신입사원 인원수
  scores = []
  for j in range(0, N):
    score = list(map(int, input().split(' ')))
    scores.append(score)
  
  scores.sort(key=lambda x:x[0])  #서류 순위 오름차순으로 정렬
  for i in range(1, len(scores)):
    top_score = min([scores[j][1] for j in range(0, i)])
    if scores[i][1] < top_score:
      cnt += 1 
  print(cnt)

 

이중 for문을 사용해서 N제곱 때문에 시간 초과가 발생하는 것 같아. 나보다 높은 면접 점수가 있는지 찾는 과정의 알고리즘을 개선할 필요성이 있었다.

 

최종 제출코드

import sys
input=sys.stdin.readline

T = int(input())
for i in range(0, T):
  N = int(input())
  scores = []
  for j in range(0, N):
    score = list(map(int, input().split(' ')))
    scores.append(score)
  scores.sort(key=lambda x:x[0])  #서류 순위 오름차순으로 정렬

  cnt = 1  #신입사원 인원수
  top_score = scores[0][1]
  for i in range(1, len(scores)):
    if scores[i][1] < top_score:
      top_score = scores[i][1]
      cnt += 1 
  print(cnt)

 

약간의 코드를 수정했다. top_score를 계산하는 부분에서 앞서 scores에 정렬을 이미 해놓았기 때문에 가장 점수가 높은 사람을 구하기 위해 for 루프와 min을 사용하지 않아도 되었다. 그리고 놓졌던 점은 내가 면접 점수가 가장 높으면 top_score를 내 점수로 바꿔 주어야 한다.