2164_Card2 - 백준

2164_card2

요구사항

• 1부터 N까지 번호가 붙고 순서대로 정렬된 카드가 입력값으로 주어지고, 제일 위에 있는 카드를 버리고 그다음 제일 위에 있는 카드를 제일 아래로 옮기는것을 반복하여 가장 마지막에 남게되는 카드를 반환한다.
  ex) 1,2,3,4 >>> 2,3,4 >>> 3,4,2 >>> 4,2 >>> 2,4 >>> result = 4

Solution

from collections import deque

nums = int(input())

# range의 두번째 인자는 해당 숫자의 앞까지 자르기 때문에 +1을 해준다.
# range를 이용하면 배열로 나오기 때문에 반복문을 돌 필요도 없다.
# deque를 이용하면 popleft(), appendleft()가 사용가능하다 - 시간복잡도 O(1)
deq = deque(range(1, nums + 1))

while len(deq) > 1:
	# deq[0]을 빼고, 그	다음 deq[0]을 젤 뒤로 보내는 것이다.
    deq.popleft()
    deq.append(deq.popleft())

print(deq.pop())

📌 코드 풀이

1. collections의 deque를 가져온다.
2. deque의 초기값을 range(1, input+1)를 이용하여 만들어 준다.
3. deque의 길이가 1이 될때까지 popleft()로 젤 앞을 버리고, append로 그다음 맨앞에 있는것을 뒤로 보내는것을 반복한다.
4. 길이가 1이 되었다면 와일문을 종료하고 최종적으로 남은 카드를 반환하게 된다.

백준

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