[백준/BOJ] - 2164번 python 풀이 - deque 자료구조 사용

---

Key Point

1. list는 random access에 특화되어있어 시간 복잡도가 높다. 하지만 deque나 que는 비교적 낮기에

이번 문제는 deque를 사용하여 해결해보았다. queue를 통해서 푸는 것도 가능은 하지만 비교적 복잡할 거 같아 보다 더 직관적인 deque를 사용하였다.

 

알게 된 문법

from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.pop() #맨 뒤부터 pop
queue.append() #맨 뒤부터 insert
queue.popleft() #맨 왼쪽부터 pop
queue.appendleft() #맨 왼쪽부터 append

 

 

---

정답 코드

from collections import deque

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

def func(arr):
    while len(arr) > 1:        
        arr.popleft()
        arr.append(arr.popleft())

        if len(arr) == 1:
            return arr
           


queue = deque([i for i in range(1,N+1)])
func(queue)
print(queue[0])

---

시간 초과 case1

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

def discard(arr):
    arr.pop(0)
    return arr


def change(arr):
    arr.append(arr.pop(0))    
    return arr

lists1 = [i for i in range(1,N+1)]

while True:
    change(discard(lists1))
    if len(lists1) == 1:
        break
print(lists1[0])

---

시간 초과 case2

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

def func(arr):
    while len(arr) > 1:        
        arr.pop(0)
        arr.append(arr.pop(0))

        if len(arr) == 1:
            return arr
           


lists1 = [i for i in range(1,N+1)]
func(lists1)

print(lists1[0])

---

시간 초과 case3

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

def func(arr):
    if len(arr) % 2 != 0: #리스트 길이 홀수
        while len(arr) > 1:                 
            arr.pop(0)  
            arr.append(arr.pop(0))          

            if len(arr) == 1:
                return arr
    else:
        while len(arr) > 1:  
            arr.append(arr.pop(0))   
            arr.pop(0)            

            if len(arr) == 1:
                return arr

if N != 1:            
    lists1 = [i for i in range(2,N+1,2)]
else:
    print(1)
    exit(0)

func(lists1)

print(lists1[0])