레벨0에서는 시간초과로 실패가 뜨는 경우가 없었는데, 레벨1에서는 시간초과로 실패가 많이 떴다. 그중 몇가지를 정리해보려고 한다.
❗제한 조건에 숫자 범위의 최댓값이 눈에 띄게 크면 시간복잡도를 고려할 것을 주의한다.❗
내 코드
소수를 찾는 간단한 문제다. 그래서 처음에는 하나씩 나눠보면서 일일이 약수의 개수를 세가며 소수인지 아닌지 판별했다. 그러나 n의 최댓값이 1000000인 것에서부터 느낌이 오듯이.. 시간초과로 실패가 주르륵 떠버렸고, 이 문제를 풀기 위해서는 '에라토스테네스의 체'를 사용해야 한다는 것을 알았다.
에라토스테네스의 체는 자연수 n이하의 모든 소수를 찾는 가장 간단하고 빠른 방법이다.
그리고 남겨진 수들이 n 이하의 소수이다.
이를 소스코드로 옮기면 다음과 같다.
import math
n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 지우기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
# 모든 소수 출력
for i in range(2, n + 1):
if array[i]:
print(i, end=' ')
에라토스테네스의 체가 뭔지 찾아보고도 코드 구현을 어떻게 할지 몰라서 비효율적인 방법으로 한 듯한데, 다음에는 위와 같은 정석적인 코드로 구현해야겠다.
내 코드
얘도 어려운 문제는 아닌데 자꾸 시간초과로 실패가 떴다. 문제의 요점은 간단하게 1부터 n까지 모든 수의 약수의 개수를 구하는 건데, 1부터 1씩 증가해가며 나눠서 나머지가 0인 것을 찾는 논리는 똑같지만 이 범위를 '1부터 n까지'가 아니라 '1부터 √n까지'로 줄여야 통과했다. 그래서 1부터 √n까지의 약수의 개수를 구해서 2배를 한 다음에, n이 제곱수인 경우에만 1을 빼줬다.
내 코드
결과값이 엄청나게 긴 "000...00"
일 때, 이를 if int("000...00") == 0
와 같이 형변환을 해서 비교하려고 하면 시간초과가 발생한다. 그래서 해당 문자열이 모두 0으로 이루어져있는지를, 0의 개수와 문자열의 길이를 비교해서 판별하는 코드로 변경해서 통과했다.
내 코드
처음엔 선수들의 순위를 리스트 메소드 index()
로 구했는데, 얘가 시간초과를 발생시켰다. 그래서 순위 딕셔너리를 따로 만들어서 순위를 가져올때의 시간복잡도가 O(1)이 되도록 변경했더니 통과했다.
이참에 자주 쓰는 메소드들의 시간복잡도를 한번 알아보도록 하자.
O(1)
- arr[i]
- len(arr)
- arr.append(i)
- arr.pop()
O(N)
- arr.insert(i,v)
- arr.pop(i)
- arr.reverse()
- for i in arr
- i in arr
- arr.count(i)
- arr.index(i)
- del arr[i]
- min(arr)
- max(arr)
- arr.remove(i)
O(NlogN)
- arr.sort()
번외로 딕셔너리는 key와 value로 바로 접근하기 때문에 반복문 도는 것 외엔 대부분 O(1)이다.