백준 2164번 카드 2 - Python

devmin24·2021년 3월 17일
0

⏳ 도전! 알고리즘

목록 보기
7/32
post-custom-banner

문제 링크 : https://www.acmicpc.net/problem/2164

풀이

이 문제는 간단하게 queue[]를 만들어 .pop()으로 왼쪽 첫번째를 지워주고 마지막에 .append()만 해주면 되는 문제였다.

첫번째 구현 - 시간초과

a = int(input())
n = [i for i in range(1, a+1)]

while len(n) > 1: # 리스트에 요소가 하나만 남을 때까지
    n.pop(0)
    n.append(n[0])
    n.pop(0)

print(n[0]) 

하지만 이렇게 제출해보니 .pop()을 두 번씩 써서인지 시간초과가 떴다. 그래서 시간을 절약할 수 있는 방법인 deque를 사용하여 다시 작성했다.

해답

import collections
a = int(input())
n = collections.deque([i for i in range(1, a+1)])

while len(n) > 1:
    n.popleft()  # 왼쪽 요소를 제거해라
    n.rotate(-1) # 왼쪽으로 한바퀴 돌려라

print(n[0])

deque를 사용하니 .pop(0)을 할 필요없이 .popleft를 쓰면 되었다. 그리고 .append와 .pop(0) 두 개를 쓸 필요없이 .rotate(-1) 하나로 해결되었다.

여기서,

  • rotate(1)은 오른쪽으로 한 칸씩 이동
  • rotate(-1)은 왼쪽으로 한 칸씩 이동

한다는 뜻이다.

profile
꾸준함, 열정 한 가득 챙겨 끝없는 목표를 향해 달려가는 개발자👩‍💻
post-custom-banner

0개의 댓글