문제 풀이들

notion.so에 따로 정리해가면서 올린 후 tistory로 임포트 시키는것이 보통 귀찮은일이 아니라, github repo에 업로드하는 형식으로 기록하는게 좋다고 생각했다.

 

그동안 공부 기록들을 포스팅하지 않은 이유는 따로 기록해둘 깨달음(?)이 없었기 때문인데, 오늘 아주 사소하지만.. 중요한것을 깨달았다.

 

파이썬 내장 함수들도 시간복잡도가 큰 경우가 있다는것.. 내장 함수들은 최선의 올기르즘으로 시간복잡도가 대부분 n이 넘지 않는다고 생각하고 있었지만, max나 min과 같은 함수들은 O(n)이기 때문에 반복문에서 해당 함수들을 사용한다면 O(n^2)의 시간복잡도를 가지게 되므로 시간초과가 뜰 가능성이 매우 높다.

 

min 함수의 시간복잡도를 생각하지 않고 짠 코드

import sys
N = int(sys.stdin.readline().rstrip())
ropes = []
for i in range(N):
    ropes.append(int(sys.stdin.readline().rstrip()))
ropes.sort(reverse=True)
for i in range(len(ropes)):
    ropes[i] = (i+1) * min(ropes[:i+1])
print(max(ropes))

min(ropes[:i+1)을 할 필요가 없는 이유는, 이미 위에서 ropes를 내림차순으로 정렬했기 때문에 min(ropes[:i+1])는 항상 ropes[i] 일 수 밖에 없다.

 

 

min의 시간복잡도를 무시하고 제출한 결과

계속 이유를 찾지 못해서,, 기회를 많이 날리고 말았다.

그래도 이 시간초과가 뜬 덕분에 min과 max을 반복문내에서 쓸 때의 시간복잡도를 생각하게 되었고, python에서 입력을 받을 때 좀 더 빠르게 입력을 받는 방법을 찾게 되었다.

 

import sys
N = int(sys.stdin.readline().rstrip())
ropes = []
for i in range(N):
    ropes.append(int(sys.stdin.readline().rstrip()))
ropes.sort(reverse=True)
for i in range(len(ropes)):
    ropes[i] = (i+1) * ropes[i]
print(max(ropes))

※ sys.stdin.readline()으로 받는것이 input()보다 빠름.