Baekjoon 문제 풀기 (2164번 : 카드2) Python

2164번 : 카드2

1. 문제읽기

---

이해하는데 어렵지 않은 문제

역시나 문제 자체를 이해하는데는 어렵지 않았다.
왜이렇게 쉽지? 하고 문제를 푸는 순간 시간초과가 떴다.
그럼그렇지…
데크로 구현하는 걸 알고도 리스트를 썼다.
그래도 안되길래 데크로 푸는 문제가 아닌가? 하고 dp 점화식만 냅다 찾아보다가 실패했다.
사실 데크 문제를 풀어본 적이 없어서 어떻게 쓰는지 대충만 알지 써본적이 없어서인 것 같다.
라이브러리와 일반 리스트의 속도 차이가 이렇게 심한지는 몰랐다.

2. 제출 코드

---

시간초과 코드는 데크 라이브러리 대신 리스트를 사용한 것만 다르므로 패스하고, 그래도 규칙을 찾으려고 노력했던 나의 노고를 기리기위해 다른 코드를 적어놓아야겠다.
1~10까지의 입력값으로 테스트 했을 때 그래도 나름 50%의 성공률을 가진 코드이다. ㅋㅋㅋ

n = int(input())

arr = [i for i in range(1, n+1)]
while 1:
    ans = []
    for i in range(len(arr)//2):
        ans.append(arr[2*i+1])
    arr = ans
    print(ans)
    if len(arr) == 1:
        break


print(arr[0])

3. 공부할 것

---

드디어 deque를 정리하는 시간이 왔다.

Collections 모듈의 deque 클래스

파이썬에서 기본 list로 deque를 구현할 수 있지만, 속도 면에서 월등히 뛰어나므로 그냥 라이브러리를 사용하자. 내장 라이브러리이기 때문에 코테에서도 사용할 수 있다고 한다.
pop 대신 popleft를 사용한다.
appendleft도 사용할 수 있다.

rotate 메소드

다른 건 list와 비슷한데 rotate 메소드는 이해가 어려워서 따로 정리해놓는다.
음수를 파라미터로 주면 요소들이 왼쪽으로 n칸씩 이동하고, 양수를 파라미터로 주면 요소들이 오른쪽으로 n칸씩 이동한다.

예제 코드

from collections import deque

arr = deque([1, 2, 3, 4, 5])

arr.rotate(-1)
print(arr)

arr = deque([1, 2, 3, 4, 5])
arr.rotate(2)
print(arr)

출력결과

deque([2, 3, 4, 5, 1])
deque([4, 5, 1, 2, 3])

정답 코드

1부터 n까지 정수를 deque에 넣어주고 왼쪽에 있는 요소를 꺼내준 뒤 왼쪽에 있는 요소를 뒤쪽에 더해준다. append 코드 대신 rotate 메소드를 써서 간단하게 나타내는 것도 가능하다.
arr가 1개만 남을때 까지 while문을 돌려주고, 그 요소를 출력하면 끝.

from collections import deque

n = int(input())

arr = deque([i for i in range(1, n+1)])

while len(arr) != 1:
	arr.popleft()
	arr.append(arr.popleft())
	# arr.rotate(-1)

print(arr[0])