[Baekjoon] 백준 알고리즘: 2164 - 카드2

문제

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

2164번: 카드2

내가 생각했던 풀이과정

 

1. 맨 앞 요소를 선택해서 버려야하고, 버린 다음의 다시 맨 앞요소를 선택해야하는 구조라서 양방향 큐(deque)를 사용하였다. 

deque를 사용할 경우에는 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

deque는 양 끝 element의 append와 pop이 압도적으로 빠르기 때문에 사용하였다.

 

2. deque의 원소가 1개 남을 때까지 반복하면서

1) 첫번째 요소는 popleft( )를 이용하여 값을 없앤다.

2) 다시 popleft( )를 하여 나온 값을 temp에 저장한후 

3) 다시 맨 뒤에 append( )를 이용하여 뒤에 삽입한다.

 

3. 원소가 1개 남으면 이를 출력한다.

나의 풀이

from collections import deque

N = int(input())
Deque = deque()
for i in range(1, N + 1):
    Deque.append(i)

while True:
    if len(Deque) != 1:
        Deque.popleft()
        temp = Deque.popleft()
        Deque.append(temp)
    else:
        print(Deque[0])
        break

다른 사람의 풀이

import sys 
from collections import deque 
N = int(sys.stdin.readline()) 
queue = deque() 

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

while len(queue) > 1: 
    queue.popleft() 
    queue.append(queue.popleft()) 
    print(queue.pop())

구조는 비슷하지만 코드가 좀더 깔끔한 것 같다.

 

새로 알게된 점, 확인해야할 점

1. 원소의 추가가 O(1) 

2. 원소의 제거가 O(1)