1946: 신입 사원

신입 사원은 입력으로 들어온 지원자들의 성적을 보고 선발 할 수 있는 최대 인원 수를 계산하는 문제이다.

중요한 조건은 성적으로 서류심사 순위와 면접시험 순위가 입력으로 주어지는데, 어떤 지원자의 성적 순위가 다른 지원자의 성적 순위에 비해 서류, 면접 순위가 모두 떨어질 경우 선발 대상에서 제외된다.

 

예를 들어서

A의 성적 순위가 각각 1, 3

B의 성적 순위가 각각 2, 1

C의 성적 순위가 각각 3, 2 라고 했을 때,

C의 성적은 A랑 비교했을 때 두 번째 성적에서는 우위에 있지만,

B랑 비교했을 때는 첫 번째, 두 번째 성적 모두 순위에서 밀린다.

이럴 경우 C는 선발 대상에서 제외되는 것이다.

 

우선 입력 조건에서 N이 100,000 까지 들어올 수 있기 때문에 O(N) 또는 O(NlogN)으로 문제를 풀어야 한다.O(N^2)으로 알고리즘을 설계하면 시간 초과 날 가능성이 굉장히 높다.

 

성적에는 두 가지 종류가 있는데 한 쪽을 오름차순으로 정렬해두고 정렬을 하지 않은 다른 성적을 서로 비교한다.정렬된 순서대로 최소 성적 순위 값을 저장하면서 최소 성적 순위 보다 후순위에 있는 사람을 선발대상에서 제외 시키면 된다.

이렇게 하면 최소 성적 순위 보다 높은 성적을 가지고 있는 사람일 경우 순위가 더 낮은 숫자로 책정될 것이고

그러면 두 번째 성적에 대해서 우위를 가지고 있는 것이기 때문에 선발 대상이 될 수 있다.

반대로 최소 성적 순위 보다 후순위에 있을 경우 오름차순으로 정렬했기 때문에 첫 번째 성적은 이미 후순위인 상태이다.

여기서 두 번째 성적 마저 후순위로 밀렸다는 뜻으로 모든 성적에서 후순위에 위치하게 되고 선발 대상에서 제외된다.

 

이렇게 코드를 구현해서 제출했었다.

 

t = int(input())
result = list()
 
for i in range(t):
  n = int(input())
  score_list = list()
  for j in range(n):
    score_list.append(list(map(int, input().split())))
 
  score_list.sort(key=lambda x:x[0])
 
  min_score = score_list[0][1]
  for score in score_list[1:]:
    if score[1] > min_score:
      n -= 1
    else:
      min_score = score[1]
 
  result.append(n)
 
for res in result:
  print(res)
 

그런데 시간 초과를 받았다..!

시간 복잡도도 고려해서 구현한 코드인데 시간 초과가 나와서 당황스러웠다.

결국 한참을 찾아본 결과 Python의 입출력 방식과 관련이 있음을 알 수 있었다.

결론부터 말하자면 input() 대신 sys.stdin.readline()을 사용하는 것이 더 좋다.

 

Python의 input()은 파라미터로 prompt에 띄우는 Message를 받을 수 있는데, 이 때문에 부하가 생길 수 있다.

하지만 sys.stdin.readline()은 prompt message를 파라미터로 받지 않는다.

또한 input()은 입력을 저장할 때 사용자가 키를 누르면 해당 키 데이터를 하나씩 버퍼에 저장하는데,

sys.stdin.readline()은 입력된 정보를 한꺼번에 읽어와서 버퍼에 저장하기 때문에 input()보다 처리 속도가 빠르다.

따라서 입력이 반복될 수록 sys.stdin.readline()이 조금 더 유리하게 작용할 수 있다.

참고로 sys.stdin.readline()을 사용하면 끝에 개행문자가 포함되기 때문에 필요에 따라 rstrip 함수를 이용하는 것도 좋다.

 

아무래도 입출력 스트림의 처리 방식 때문에 서로 유의미한 속도 차이가 나는 것 같다.

실제로 반복해서 입력을 받아오는 곳에 input() 대신 sys.stdin.readline()을 사용했더니 정답 판정을 받을 수 있었다.

구글링을 하다보니 이 문제 때문에 시간 초과로 코딩 테스트에서 문제를 풀지 못한 사람도 있다고 하니 꼭 알아둬야겠다..

 

import sys
 
t = int(input())
result = list()
 
for i in range(t):
  n = int(input())
  score_list = list()
  for j in range(n):
    score_list.append(list(map(int, sys.stdin.readline().split())))
 
  score_list.sort(key=lambda x:x[0])
 
  min_score = score_list[0][1]
  for score in score_list[1:]:
    if score[1] > min_score:
      n -= 1
    else:
      min_score = score[1]
 
  result.append(n)
 
for res in result:
  print(res)