🚗현대인을 위한 3줄요약.
python의 표준 라이브러리
deque를 사용하면list를 사용했을때 보다 메모리 활용이나 러닝타임에 있어 효율적이다.
📌전체코드
👉 이전 포스트에서 언급된 내용은 따로 언급하지 않습니다.
우선 전체 코드는 다음과 같다.
import sys
from collections import deque # deque 라이브러리 사용
input = sys.stdin.readline
num = int(input())
# 1부터 num까지의 숫자로 이루어진 deque 생성
card = deque([i for i in range(1, num + 1)])
while(len(card) > 1): # card의 원소 개수가 1개가 될때 까지 반복
card.popleft() # 가장 왼쪽의 원소 제거
card.rotate(-1) # 역방향으로 deque 1회 순환
print(card[0])해당 코드에서 면밀히 살펴볼 부분은 다음과 같다.
deque: python의 표준 라이브러리popleft & rotate: deque의 내장 메소드
각 키워드가 포함된 문단별로 나눠서 분석해보자
👉deque
# list를 사용한 코드
card = [i for i in range(1, num + 1)]
while(len(card) > 1):
card.append(card[1])
del card[0:2]
print(card[0])deque 은 queue 의 일종으로 양방향인 queue이다. 얼핏보기엔 list 와 큰 차이가 없다. 그럼 list가 아닌 deque를 사용하는 이유가 무엇일까?
바로 deque이 list 보다 월등히 빠르기 때문이다. 단순히 시간복잡도를 따졌을 때 list는 O(n), deque는 O(1) 으로 상당히 빠르다는것을 알 수 있다.
👉popleft & rotate
popleft 와 rotate(n)는 deque의 내장 함수로 각각 가장 왼쪽의 원소를 제거, 지정된 방향으로 n만큼 회전한다는 뜻이다. popleft는 말 그대로 이해하기 쉬우나 rotate는 텍스트만으로는 이해하기 어려울 수 있다.
doTest = deque([i for i in range(1, 6)])
# 실행결과 : deque([1, 2, 3, 4, 5])여기 doTest 라는 deque이 있다. doTest에는 1 ~ 5까지의 숫자를 저장해 두었다. 여기서 doTest를 정방향 으로 1회 회전한다고 하면 다음과 같다.
card.rotate(1)
# 실행결과 : deque([5, 1, 2, 3, 4])최후방의 원소 1개(5)가 맨 앞으로 간것을 확인할 수 있다. 역방향의 경우 n 의 자리에 음수를 대입해주면 된다.
card.rotate(-2)
# 실행결과 : deque([3, 4, 5, 1, 2])최전방의 원소 2개(1, 2)가 차례대로 맨 뒤로 간것을 확인할 수 있다.
📌다른 방법
본 문제는 deque을 사용하여 러닝타임을 단축해 넘어갈 수 있었지만 간혹 이런 방법으로도 해결되지 않는 경우가 있다(많다). 그럴경우 진리표 를 작성해 가며 각 action간의 규칙 을 찾아내는 수학적 접근 을 해야한다.
각 action간의 규칙을 찾기 위해 진리표를 작성하였다. 사진에서는 잘려서 밑부분이 보이지 않지만 N = 8 일때의 action까지 기록하였고 요약하자면 다음과 같다.
- 3일 때 : (3 - 2) * 2 = 2
- 4일 때 : (4 - 2) * 2 = 2
- 5일 때 : (5 - 4) * 2 = 2
- 6일 때 : (6 - 4) * 2 = 4
- 7일 때 : (7 - 4) * 2 = 6
- 8일 때 : (8 - 4) * 2 = 8
즉 [ N - 2 ** (N > 2의 제곱) ] * 2 이다.
해당 규칙을 참고하여 코드를 작성하면 다음과 같다.
input = int(input())
square = 2
while True:
if (input == 1 or input == 2):
print(input)
break
square *= 2
if (square >= input):
print((input - (square // 2)) * 2)
break
# 사실 나는 규칙을 찾지 못해서 다른 사람의 포스트를 참고하였다.
출처: https://tooo1.tistory.com/88 [개발자 퉁이리:티스토리]이렇듯 수학적 접근을 통해 문제를 해결하면 시간복잡도가 상당히 감소하지만 그만큼 어렵고 시간도 많이걸린다.
참고문서
