[알고리즘] 백준 2164 (파이썬 풀이)

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

2164번: 카드2

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

해결코드

import sys
from collections import deque

n = int(sys.stdin.readline())
li=deque()

for i in range(n):
    li.append((i+1))
while(True):
    if(len(li)==1):
        break
    li.popleft()
    li.append(li[0])
    li.popleft()
print(li[0])

문제풀이

이 문제는 딱봐도 시간복잡도가 꽤나 나올 것으로 예상이 됐지만 한번 먼저 무식하게 풀어봤다.

일단 이 문제는 큐, 덱과 비슷한 문제인데, 약간 변형이 되었다.

문제푸는 순서는 n에 수를 입력을 받고 1부터 n까지의 원소를 가진 리스트를 만든다.

그 리스트를 조건에 맞게 계속해서 변형하다가 마지막까지 남은 원소를 출력해야하는 문제이다.

처음 문제를 풀 때는

import sys

n = int(sys.stdin.readline())
li=[]

for i in range(n):
    li.append((i+1))
while(True):
    if(len(li)==1):
        break
    li.pop(0)
    li.append(li[0])
    li.pop(0)
print(li[0])

이런 식으로 풀었더니 당연하게도(?) 시간초과가 났다. 저기 while문 안쪽 pop,append를 모두 출력해보면

 

n에 4를 입력했을 때조차도 엄청나게 조잡해진다. 답은 나오지만..

 

사실 이럴 경우네는 내장 라이브러리를 사용하면 시간복잡도를 간단하게 줄일 수 있다.

라이브러리를 선언하고 li를 배열이 아닌 deque()로 선언, li.pop(0)을 li.popleft()로 변경해주면

문제를 해결할 수 있다.

정답 코드도 좀 조잡해보여서 앞으로는 더 깔끔하게 코딩할 수 있도록 해야겠다..ㅎ