19637 IF 좀 대신 써줘

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

"""
전투력 시스템

10000<= WEAK
10000< <=100000 NORMAL
100000< <=1000000 STRONG
"""

import sys
read = sys.stdin.readline
N,M = map(int,read().split())
award_list = []
score_list = []
for _ in range(N):
    award, score = read().split()
    if len(score_list) == 0 or score_list[-1] != score :
        award_list.append(award)
        score_list.append(int(score))

val_list = []
for _ in range(M):
    temp_val = int(read())

    start_idx = 0
    end_idx = len(award_list)-1

    while start_idx <= end_idx :
        mid_idx = (start_idx+end_idx)//2
        if score_list[mid_idx] >= temp_val :
            end_idx = mid_idx - 1
        else :
            start_idx = mid_idx + 1
    print(award_list[start_idx])

3. 풀이 및 생각

문제 풀이

매우 평범한 이진탐색 문제이므로 풀이는 생략.

나의 생각

음 이 문제 처음에 접했을 때, 같은 스코어를 가진 칭호들이 있었다. 이를 해결하기 위해 짠 첫 코딩은 다음과 같았다.

  if score not in score_list :
      award_list.append(award)
      score_list.append(int(score))

근데 여기서 중요한 점이 if score not in score_list 를 쓰면, score_list를 전부 훑기 때문에 O(len(score_list))의 시간복잡도를 생각해야한다. 계속 시간초과가 떴던 이유는 바로 이것! 그래서 다음과 같이 코드를 바꿨더니 문제가 해결 되었다. 최대한 이 예시를 기억하자.

  if len(score_list) == 0 or score_list[-1] != score :
      award_list.append(award)
      score_list.append(int(score))