백준 2164번 파이썬 풀이

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

결론 미리 보기

 

파이썬에서 string slicing은 시간복잡도 N(len(str))이므로
특정 인덱스의 글자에 접근할 때는
list로 만들어 접근하는 것이 시간복잡도 O(1)로 빠르다!

 

 

가장 직관적으로 짤 수 있는 코드는 아마 아래의 코드일 것이다. 

import sys
N=int(sys.stdin.readline())
st=''

for i in range(N):
    st+=str(i+1)

for i in range(N-1):
    st=st[1:]
    fir=st[0]
    st=st[1:]
    st+=fir

print(int(st))

이 코드를 사용하면 정답은 풀리는데 시간 초과가 뜬다. 제한 시간이 2초이다. 프로그램의 실행 속도를 확인해 보았다.

import time
start_time = time.time()	# 측정 시작

# 프로그램 소스코드
end_time = time.time()		# 측정 종료
print('time:', end_time - start_time)	# 수행 시간 출력

이 코드를 사용해 측정해 보았더니

6을 입력해도 1.15초가 소요되는 것을 볼 수 있다. 문제 조건은 N <5000000이므로

5000000을 넣으면 2초가 훨씬 넘게 소요되는 코드인 것을 예상할 수 있다.

실제로 5000000을 넣으면 몇 분을 기다려도 결과가 출력되지 않는다.

따라서 파이썬의 시간복잡도 기준을 따져보았을 때 O(N) 정도의 시간복잡도를 가진 코드를 짜는 것이 이상적이다.

 

 

내 코드는

두 번째 반복문의 내부 반복문에서

1. st 문자열을 한 번 슬라이싱 하고,
2. 그 후 첫 번째 문자를 추출하여 다시 st 문자열에 붙임.
3. 이 과정은 N-1번 반복
4. 슬라이싱은 문자열의 길이에 비례하는 작업이므로, 슬라이싱 자체의 시간 복잡도는 O(len(st))
5. 따라서 두 번째 반복문의 시간 복잡도는 대략 O((N-1) * len(st)).
6. 그러나, 슬라이싱이 문자열 길이에 비례
7. st 문자열의 길이는 처음에 1부터 N까지의 숫자를 이어 붙인 문자열로서 대략 O(N * log10(N)) 정도의 길이
8. 예를 들어, N=10이라면 12345678910 이 되므로 약 11자리의 숫자
9. 따라서 두 번째 반복문의 시간 복잡도는 O((N-1) * O(N * log10(N)))로 정확하게 표현하면 O(N^2 * log10(N)) 정도

즉 시간복잡도가 N^2가 넘는다!

문제는 문자열 길이만큼의 슬라이싱을 하다 보니 이 슬라이싱이 이미 O(N)을 잡아먹는 것!

 

따라서 str 슬라이싱 대신 list를 사용해 deque의 popleft() 메서드를 사용했다. 파이썬은 stack은 list로 구현이 가능하고, queue는 

from queue import Queue / from collections import deque

를 해서 사용하면 된다.

 

import sys
from collections import deque

N=int(sys.stdin.readline())
li=[]

for i in range(N):
    li.append(i+1)

li=deque(li)
for i in range(N-1):
    li.popleft()
    fir=li[0]
    li.popleft()
    li.append(fir)


print(li[0])

list의 인덱싱은 N(1)이기 때문에 시간복잡도가 확연히 작아졌다.