백준 2164번(카드2) - 큐, 자료구조

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

 

 

❓ python 풀이 - 규칙 찾아서 풀었따...

내가 생각한 규칙은

1(2^0)	1
2(2^1)	2
3	2*(3-2) = 2
4(2^2)	4
5	2*(5-4) = 2
6	2*(6-4) = 4
7	2*(7-4) = 6
8(2^3)	8
9	2
10	2*(10-8) = 2
11	2*(11-8) = 2
12	2*(12-8) = 2
13	2*(13-8) = 2
14	2*(14-8) = 2
15	2*(15-8) = 2
16(2^4)	16

1. 2의 거듭제곱인 경우:
   • 2의 거듭제곱에 해당하는 수는 그대로 남습니다. 예를 들어, 1, 2, 4, 8, 16은 그대로 해당 값이 남습니다.
   • 즉, 2^n인 경우 마지막 남는 카드는 그 값 그대로입니다.
2. 2의 거듭제곱보다 큰 수인 경우:
   • 2의 거듭제곱을 기준으로 해당 수(N)에서 거듭제곱을 뺀 후, 그 값에 다시 2를 곱한 결과가 마지막에 남는 카드가 됩니다.
   • 예를 들어, N = 3일 때 N이 2와 4 사이에 있으므로, N - 2 = 1이고 2 * 1 = 2가 마지막에 남습니다.
   • N = 5일 때, N - 4 = 1, 2 * 1 = 2가 마지막에 남습니다.
   • N = 6일 때, N - 4 = 2, 2 * 2 = 4가 마지막에 남습니다

#처음 생각한 풀이
import sys

i = int(sys.stdin.readline().strip())  # 카드의 개수를 입력받음
s = i #s에 i를 복사함

count = 0 #2의 거듭제곱 찾기 위해서 사용된 변수
# i보다 작은 가장 큰 2의 거듭제곱을 찾기 위한 반복문
while s // 2 > 0:
    count += 1
    s = s // 2

# 마지막 남은 카드 계산
# 2의 거듭제곱이 아닌 경우, 남은 카드를 계산
if i != pow(2, count):
    print((i - pow(2, count)) * 2)
else:
    print(i)

import math
import sys

def last_card(n):
    # 2의 거듭제곱이 아닌 경우를 처리하기 위해 가장 큰 2의 거듭제곱을 찾음
    if n == 1:
        return 1  # N이 1이면 그대로 1이 남음

    # N보다 작거나 같은 가장 큰 2의 거듭제곱 찾기
    highest_power_of_two = 2 ** int(math.log2(n)) #log2를 이용하면 2의 거듭제곱 값 구할 수 있음

    # 입력하는 N이 2의 거듭제곱인 경우
    if highest_power_of_two == n:
        return n

    # 입력하는 N이 2의 거듭제곱이 아닌 경우
    return (n - highest_power_of_two) * 2


# 입력 받기
N = int(sys.stdin.readline().strip())

# 결과 출력
print(last_card(N))

 

❓ python 풀이 - 큐로 푼 경우

from collections import deque # 큐 import
import sys

N = int(sys.stdin.readline().strip())
cards = deque(range(1,N+1)) # 1부터 N까지의 숫자를 큐에 넣음

# 카드가 한 장 남을 때까지 반복
while len(cards)>1:
    cards.popleft() # 첫 번째 카드를 버림
    cards.append(cards.popleft()) # 그다음 카드를 맨 아래로 옮김

print(cards[0])