알고리즘 챌린지 시즌 2 - 6일차

💡

학교 동아리에서 주최하는 알고리즘 챌린지에 참여하다가 몰랐던 부분에 대해 작성한 글입니다.

백준 2164번

---

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

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

• 시간 초과가 발생했던 코드

n = int(input())

card = []
for i in range(1, n + 1):
    card.append(i)

def card2(a):
    while len(a) != 1:
        a.pop(0)
        left = a.pop(0)
        a.append(left)
        #card2(a)
    return a[0]

print(card2(card))

→ 찾아보니까 시간복잡도 때문에 시간 초과가 발생한 것으로 보였다. 구글링을 해보니 deque아니면 직접 규칙을 찾아서 해결하는데, deque가 뭔지 몰랐기에 이번 기회에 정리해보고자 한다.

deque

---

Stack 이나 queue 처럼 한 방향에서 삽입과 삭제가 일어나는 것이 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다.

💡

리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 뒤에 있는 원소들을 하나씩 앞으로 당겨주는 연산도 하게 된다. 따라서 리스트의 삭제 연산은 O(n)이 걸린다. 반면 deque의 삭제 연산은 O(1)이다. 따라서 push, pop 이 자주 쓰이는 알고리즘이면 list보다 deque를 사용하는 것이 효율적이다.

이런 이유 때문에 내가 생각했던 코드에서 시간초과가 발생한 것 같다.

deque 생성

from collections import deque
dq = deque('love')
print(dq)

# 출력 : deque(['l', 'o', 'v', 'e'])

스택구현 : append(), pop()

dq.append('m')                # 오른쪽에 넣기
print(dq)

# 출력 : deque(['l', 'o', 'v', 'e', 'm'])


dq.pop()                      # 오른쪽 요소 반환
print(dq)

# 출력 : deque(['l', 'o', 'v', 'e'])

큐 구현 : appendleft(), pop(), append(), popleft()

dq.appendleft('I')             # 왼쪽에 넣기
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e'])


dq.append('y')                 # 오른쪽에 넣기
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e', 'y'])


dq.popleft()                   # 왼쪽 요소 반환
print(dq)

# 출력 : deque(['l', 'o', 'v', 'e', 'y'])

deque 확장 : extend(), extendleft()

dq.extend('ou')                 # 오른쪽으로 확장
print(dq)

# 출력 : deque(['l', 'o', 'v', 'e', 'y', 'o', 'u'])


dq.extendleft('I')              # 왼쪽으로 확장
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e', 'y', 'o', 'u'])

리스트처럼 사용 : insert(), remove()

dq[2] = 'n'                # 'o' -> 'n'
print(dq)

# 출력 : deque(['I', 'l', 'n', 'v', 'e', 'y', 'o', 'u'])

dq = deque('love')
dq.insert(0, 'I')          # 0번째 항목에 'I'추가
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e'])


dq.insert(100, 'K')         # 100번째 항목(없으니 가장 오른쪽에) 'K'추가
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e', 'K'])


dq.remove('K')              # 'K'삭제, 만약 같은 항목이 있다면 왼쪽부터 삭제됨.
print(dq)

# 출력 : deque(['I', 'l', 'o', 'v', 'e'])

deque 내용 반전 : reverse()

dq.reverse()
print(dq)

# 출력 : deque(['e', 'v', 'o', 'l', 'I'])

참고한 블로그 : https://duckracoon.tistory.com/entry/파이썬-collections-deque-사용법과-응용, https://dongdongfather.tistory.com/72

deque이용해서 다시 구현한 코드

---

from sys import stdin
from  collections import deque

n = int(stdin.readline())

q = deque()

for i in range(1, n + 1):
    q.append(i)

while len(q) != 1:
    q.popleft()
    q.append(q.popleft())

print(q[0])

Uploaded by Notion2Tistory v1.1.0