[백준] 2164: 카드2 - 파이썬[python]

문제 의도대로 큐를 이용해서 풀면서 분명히 규칙을 찾으면 시간을 엄청나게 단축시킬 수 있을 거라는 생각이 들었다. 그래서 큐로 푼 버전, 규칙을 찾아서 푼 버전 2개로 풀어보았다.

1. 큐 이용

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
queue = deque(i+1 for i in range(N))

while len(queue) != 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

2. 규칙 이용

import sys
input = sys.stdin.readline

N = int(input())
temp = N
num = 0
while temp != 1:
    num += 1
    temp //= 2

if N%(2**num) == 0:
    print(2**num)
else:
    print(2*(N%(2**num)))

출력값 나열해보기

• 규칙을 찾기 위해 1~16까지 출력값을 나열해 보았다.
  1:1 2:2 3:2 4:4 5:2 6:4 7:6 8:8 9:2 10:4 11:6 12:8 13:10 14:12 15:14 16:16
• 4일 때 4, 8일 때 8, 16일 때 16임에 주목하였다. 이게 2의 거듭제곱에 따른 규칙일 거라는 의심이 들었고, 혹시나 4의 배수에 의한 규칙은 아닌지 확실하게 하기 위해 32까지도 나열해 보았다.
  17:2 18:4 19:6 20:8 21:10 22:12 23:14 24:16 25:18 26:20 27:22 28:24 29:26 30:28 31:30 32:32
• 음 맞구만!

그룹으로 나누어보기

0. 1:1=2^0
1. 2:2=2^1
2. 3:2 4:4=2^2
3. 5:2 6:4 7:6 8:8-2^3
4. 9:2 10:4 11:6 12:8 13:10 14:12 15:14 16:16=2^4
5. 17:2 18:4 19:6 20:8 21:10 22:12 23:14 24:16 25:18 26:20 27:22 28:24 29:26 30:28 31:30 32:32=2^5

• 이런 식으로 그룹이 나누어지겠다.
• 그룹 안에서 또 규칙을 찾으려고 했다.
• 각 그룹에서 순서대로 2의 배수인 것에 주목했다.
• 예를 들어 5그룹의 19를 분석해보자. 6 = 23 = 2(19//16) = 2*(19//2**4)로 표현할 수 있겠다.

식으로 코드 짜보기

while temp != 1:
    num += 1
    temp //= 2

• 그래서 주어진 수에 작은 2의 거듭제곱수 중 가장 큰 값이 무엇인지 찾기 위해 위 식으로 num을 구했다.

2*(N%(2**num))

• 이렇게 구한 num 값을 이용해서 아까 표현했던 식으로 바꾸어주었다.
• 그런데 N이 2의 거듭제곱이면 나머지 즉, N%(2**num) 값이 0이 되어서 출력값은 0이 된다.

N%(2**num)

• 그래서 N이 2의 거듭제곱인지 확인하는 과정을 추가한다.

2-1. 규칙 + log 이용

• 너무 복잡해서 이게 맞나? 다른 더 좋은 방법은 없나? 찾아봤다.
• 여러 방법들이 나오는데 내가 규칙을 좀 복잡하게 찾아서 그렇지 베이스(?)는 비슷한 것 같았다.
• log로 num값을 찾으면 코드가 더 쉽게 나오겠더라!!

import sys, math
input = sys.stdin.readline

N = int(input())
num = int(math.log2(N))

if N%(2**num) == 0:
    print(2**num)
else:
    print(2*(N%(2**num)))

• 파이썬의 math함수는 밑이 2, 10, e인 log를 지원해준다.

• 왜 시간이 더 느는지는 모르겠당ㅎ

2-1을 더 간단히 써보자.

• 보니까 굳이 나머지를 이용하지 않고 N에서 바로 거듭제곱값을 빼도 되겠더라.

import sys, math
input = sys.stdin.readline

N = int(input())
num = int(math.log2(N))

result = 2*(N-(2**num))
if result == 0:
    print(N)
else:
    print(result)

결론

• 큐를 이용하는 문젠데 규칙찾기에 엄청나게 머리 쓴 문제 ㅎ
• 시간 내에 해결이 된다면 무작정 시간을 줄이는 규칙만 찾는 게 아니라 효율적인 알고리즘을 사용하는 게 좋은 코드라는 걸 가르쳐준 문제다.