백준 1946 - 파이썬

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

1946번: 신입 사원

 

문제 풀이

가장 처음 해야 할 것은 성적을 오름차순으로 정렬하는 것이다. 어차피 서류평가 성적이나 면접시험 성적 중 하나라도 다른 지원자들보다 높으면 합격을 하기 때문이다. 그 후 나머지 성적을 비교해 합불을 따지면 된다.

 

여기까지 아이디어를 떠오리는데 오랜 시간이 걸리지 않았고, 곧바로 코드로 작성할 수 있었다.

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
  n = int(input())
  rank = [list(map(int, input().split())) for _ in range(n)]
  rank_asc = sorted(rank)
  result = 1

  for i in range(len(rank)):
    if i == len(rank_asc) - 1:
      break
    if rank_asc[i][1] > rank_asc[i+1][1]:
      result +=1

  print(result)

하지만 이 코드의 문제는 이미 불합격 판정이 나서 더이상 비교하지 않아도 될 지원자의 성적까지 매 반복문마다 비교하여 최적화를 실패하였다는 것이다. 계속 고민하다가 해결 방법을 찾지 못해서 다른 사람의 풀이를 찾아 보았다.

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
  n = int(input())
  rank = [list(map(int, input().split())) for _ in range(n)]
  rank_asc = sorted(rank)
  result = 1
  top = 0

  for i in range(1, len(rank_asc)):
    if rank_asc[i][1] < rank_asc[top][1]:
      top = i
      result +=1

  print(result)

차이점은 top이라는 변수를 사용하여 합격한 지원자의 인덱스를 기록해두고 불합격한 지원자의 인덱스는 넘겨 합격한 사람의 성적만 비교하여 최적화를 시킨 것이다.

 

이 문제를 풀면서 느낀점은 변수 하나를 더 사용하여 조건에 총족한 경우에만 해당 인덱스 번호를 저장하여 그 번호와 비교하여 최적화를 하는 방법이다. 다음 번에도 이런 문제가 나온다면 해당 방법을 활용해 보는것이 좋을 거 같다.