각 i단계를 통과한 개수를 구한다. = 각개수[i]로 포현 그리고 각 개수에대한 누적합을 구하고 실패율을 구할 수 있는 일반식을 도출하여 실패율을 구한다.
문제를 꼼꼼히 읽고 간단히 구현만 하면 되는 문제였다. 단 단순히 전체를 탐색하면서 O(500) * O(200000) 연산을 통해서 풀면 1억번이 넘어간다. 그러므로 항상 더 나은 방법이 없는지 생각하면서 풀어보자!
최종코드
from collections import defaultdict
def solution(N, stages):
nums = [None] + [0]*(N+1)
prefix_sum = [0]*(N+2)
# 각 개수 합 구하기
for x in stages:
nums[x] += 1
# 누적 합 구하기
for i in range(1, len(nums)):
prefix_sum[i] = prefix_sum[i-1] + nums[i]
# 실패율 key, value 쌍구하기
fail = defaultdict(int)
for i in range(1, N + 1):
if nums[i] == 0:
fail[i] = 0
continue
fail[i] = nums[i] / (prefix_sum[-1] - prefix_sum[i-1])
# 실패율이 낮은 순으로 정렬
ans = []
for x, y in sorted(fail.items(), key = lambda x : x[1], reverse = True):
ans.append(x)
return ans
-> 보통 시간복잡도에 살짝 애매하게 걸리면 완전탐색말고 일단 이진탐색이나, 분할정복 혹은 누적합등의 방법을 고려해서 생각해본다. 그러면 대부분 이중에 하나로 잘 풀렸다. dp 나 백트래킹의 경우 문제를 읽다보면 특유의 느낌(문제 형식에서 나오는 익숙함)이 오니까 그럴때만 사용하자!
