[알고리즘 스터디] 백준 2164번 Python 풀이 - 카드2 (연산 복잡도, deque, 식 세우기)

# 문제

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

2164번: 카드2

# 시도 1 (실패 - 시간초과)

number = int(input())

array = [i+1 for i in range(number)]

length = number

while (len(array) != 1):
    del array[0]
    item = array.pop(0)
    array.append(item)
    print(array)

print(array[0])

array의 pop 연산자와 del을 사용해 문제를 해결하려고 함 -> 시간 초과 

- del의 연산복잡도 -> O(N)

https://wayhome25.github.io/python/2017/06/14/time-complexity/

 

# 시도 2 (성공)

import sys
from collections import deque

input = sys.stdin.readline

number = int(input())

array = [i+1 for i in range(number)]

deq = deque()
deq.extend(array)

while (len(deq) != 1):
    deq.popleft()
    item = deq.popleft()
    deq.append(item)

print(deq[0])

시간 초과 문제를 해결하기 위해 deque를 import하고 deque의 popleft와 같은 method를 사용함. 

(참고한 글 - https://leonkong.cc/posts/python-deque.html )

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우,
일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1) 로 접근 가능하다.

# 시도 3 (성공)

import math

# 2^n - x (input) -> 2^n - 2*x (output)
# 규칙 찾기
# 2^n - x = a
# 2^n = x + a
# n = log2(x + a) = ceil(log2(x+a))


def solve():
    a = int(input())
    n = math.ceil(math.log2(a))
    x = 2**n - a
    print(2**n - 2 * x)


solve()

유튜브에서 찾은 풀이 -> 규칙 찾아서 식 세우고 풀이에 적용 

https://www.youtube.com/watch?v=RUoJt2VKGk0&t=1s 

 

# 새롭게 알게 된 것 

- array의 주요 연산자의 시간 복잡도를 고려해야 한다는 것 

- del의 연산 복잡도는 O(N)임 

- deque의 연산 대부분은 O(1) 복잡도를 가짐

- 규칙을 찾아서 풀 수도 있다는 것

   -> 규칙을 찾을 때 시간 초과가 났던 코드에 예시 코드를 대입하여 규칙을 찾는 것도 방법임. 

   -> (의문) 식은 어떻게 세우지?