[python]2164_카드2

1 걸린 시간 : 1h

2 사용한 자료구조 및 개념 : deque, 수학적 규칙성 찾기

---

💡 문제풀이 아이디어 및 어려웠던 점

---

💫 아이디어

    1️⃣ deque를 활용

• popleft() 로 제일 위에 있는 카드를 버림
• append.(q.popleft()) 로 제일 위에 있는 카드를 제일 아래로 옮김

---

    2️⃣ 수학적 규칙을 찾는다

• 2의 거듭제곱이면, n 자체가 마지막으로 남음
• 2의 거듭제곱이 아니면, n에서 가장 가까운 2의 거듭제곱 p(p < n) 만큼 떨어진 곳 * 2 의 수가 제일 마지막에 남게 됨

---

👻 어려웠던 점

• deque를 사용하면 쉬운 문제지만 수학적 규칙성을 찾을려고 해서 시간이 조금 걸렸다.
  deque를 사용하고 싶지 않았던 이유가 pop/append가 많이 사용되는데
  deque의 길이가 길 경우 비효율적이라 생각하여…수학적 규칙으로 풀고싶었다..

저번에 요세푸스 문제를 풀고 n을 리스트의 길이로 나눈 나머지를 인덱스로 활용하여 원소를 삭제했는데..이 방법은 아니었다..ㅠ 예시문제만 이 규칙으로 풀리고 다른 경우는 틀림..!
리스트의 요소들을 옮기지 않고 삭제하는 방식으로만 하고싶었는데 어렵군..

 

| 틀린 풀이

# 틀린 거!
n = int(input())

arr = list(range(1, n + 1))
idx = 0
while len(arr) > 1:
    idx = n % len(arr)
    del arr[idx]

print(*arr)

그래서 그냥 수학적 규칙 찾아봤다^.^
2의 거듭제곱!!

Solution Code & 주석
deque를 활용한 코드

from collections import deque

n = int(input())
queue = deque(range(1, n+1))

while len(queue) > 1:
    queue.popleft()  # 제일 위에 있는 카드를 버림
    queue.append(queue.popleft())  # 제일 위에 있는 카드를 제일 아래로 옮김

print(queue[0])  # 마지막으로 남은 카드 출력

---

2의 거듭제곱 활용한 코드

n = int(input())

# 가장 가까운 작은 2의 거듭제곱 찾기
p = 1
while p * 2 <= n:
    p *= 2

# 결과 계산
if n == p:
    print(n)
else:
    print((n - p) * 2)

⚡충격적인 풀이

n,p = int(input()), 1
while p < n:
    p *= 2
print(2*n-p)