[Algorithm] 🚩[백준] 1225 (Feat. 시간복잡도)

a, b = map(str, input().split())

sum = 0
for i in a:
    for j in b:
        sum += int(i)*int(j)

print(sum)

시간 초과가 뜬다.. A, B가 10,000 자리를 넘지 않는다는 조건이 있고, 내가 작성한 코드는 가장 오래 걸리는 경우 100,000,000 이다. 그럼 O(N^2) 이라서 될 줄 알았는데.. 찾아보니 파이썬이 느린 편이라 예측을 벗어나 시간 내에 안 돌아가는 경우도 있다고 한다.

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다.

pypy3로 제출하면 된다고 하지만 그냥 시간 복잡도를 줄여서 풀어봐야겠다.
시간복잡도를 O(N^2)에서 O(N)로 바꿀 수 있는 방법이 있다!

a, b = map(str, input().split())

atmp = 0
btmp = 0

for i in a:
    atmp += int(i)
for j in b:
    btmp += int(j)

print(atmp*btmp)

n번만큼 반복하는 반복문이 2개이다. 이것은 O(N^2)가 아닌 O(N)이다!
O(N)은 반복문이 하나가 있으나 수십개가 있으나 O(N)인 것을 명심하자.

<참고>
https://coding-factory.tistory.com/608