[Python] 2164. 카드2

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

---

 

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

 

풀이

입력 케이스를 직접 하나하나 써내려가면서 규칙을 찾아내야 하는 문제이다... 이런 문제에 제일 약하다ㅜ

규칙을 찾기 위해 입력이 1~10일 때 출력 결과를 전부 써 보았다.

 

1 -> 1 (2^0)
1 2 -> 2 (2^1)
1 2 3 -> 3 2 -> 2 (3-2)x2
1 2 3 4 -> 3 4 2 -> 2 4 -> 4 (2^2)
1 2 3 4 5 -> 3 4 5 2 -> 5 2 4 -> 4 2 -> 2 (5-4)x2
1 2 3 4 5 6 -> 3 4 5 6 2 -> 5 6 2 4 -> 2 4 6 -> 6 4 -> 4 (6-4)x2
1 2 3 4 5 6 7 -> 3 4 5 6 7 2 -> 5 6 7 2 4 -> 7 2 4 6 -> 4 6 2 -> 2 6 -> 6 (7-4)x2
1 2 3 4 5 6 7 8 -> 3 4 5 6 7 8 2 -> 5 6 7 8 2 4 -> 7 8 2 4 6 -> 2 4 6 8 -> 6 8 4 -> 4 8 -> 8 (2^3)
1 2 3 4 5 6 7 8 9 -> 3 4 5 6 7 8 9 2 -> 5 6 7 8 9 2 4 -> 7 8 9 2 4 6 -> 9 2 4 6 8 -> 4 6 8 2 -> 8 2 6 -> 6 2 -> 2 (9-8)x2
1 2 3 4 5 6 7 8 9 10 -> 3 4 5 6 7 8 9 10 2 -> 5 6 7 8 9 10 2 4 -> 7 8 9 10 2 4 6 -> 9 10 2 4 6 8 -> 2 4 6 8 10 -> 6 8 10 4 -> 10 4 8 -> 8 4 -> 4 (10-8)x2

 

직접 써 보고 나니, 등비수열이 반복되는 것이 눈에 보였다. 입력값이 2의 거듭제곱이면 출력값은 그대로, 그 외의 수일 때는 그 수보다 작으면서 가장 큰 2의 거듭제곱과 관련이 있다는 것을 알게 되었다. 즉

입력값이 N일 때,
1) N이 2의 거듭제곱
=> N 출력
2) 그 외
=> N보다 작으면서 가장 큰 2의 거듭제곱이 L일 때 ( N - L ) X 2 출력

 

파이썬에서 특정 수가 2의 거듭제곱인지 판단하는 로직을 찾아보니 비트 연산으로 계산하는 법이 있길래 활용하였다.

특정 수보다 작으면서 가장 큰 2의 거듭제곱을 찾는 데는 while문을 활용하였다.

첫 번째 코드

import sys

input = sys.stdin.readline

n = int(input())
if (n & (n - 1)) == 0:
    print(n)
else:
    latest = 1
    while latest * 2 < n:
        latest *= 2
    print((n - latest) * 2)

복잡한 자료 구조를 사용하지 않고 수학적 규칙을 찾은 뒤 직관적으로 잘 구현한 것 같다.

다만 다른 사람들의 제출 코드를 살펴보는데 더 효율적인 방법으로 구현한 코드를 찾게 되어 그 방법을 적용해 보았다.

 

N 이하의 가장 큰 2의 거듭제곱 값 찾기: 1 << (N.bit_length() - 1) 사용

: 기존 코드에선 N보다 작으면서 가장 큰 2의 거듭제곱 값을 찾기 위해 while 문을 사용하였다.

그러나 1 << (N.bit_length() - 1) 을 사용하면 단 한 줄로 N 이하의 가장 큰 2의 거듭제곱 값을 찾을 수 있다.

원리는 아래에서 설명

최종 코드

import sys

input = sys.stdin.readline

n = int(input())
l = 1 << (n.bit_length() - 1)

if n == l:
    print(l)
else:
    print((n - l) * 2)

 

비트 연산을 잘 알수록 더 깔끔하고 간단한 코드를 작성할 수 있다는 걸 깨달았다...

비트 연산에 대해 잘 모르지만 조금씩 공부하면서 이런 알고리즘 구현 문제에서 적절히 활용할 수 있도록 노력해봐야겠다.  

배운 것

• n & (n - 1) : n이 2의 거듭제곱인지 판단하는 로직이다. n과 n-1을 비트연산(AND)하게 될 경우, n이 2의 거듭제곱이면 결과값은 항상 0, 아닐 경우 1이 출력된다. (n=1일 때도 결과값 0 출력)
• 1 << (n.bit_length() - 1): n 이하의 가장 큰 2의 거듭제곱 값을 출력한다.
  
  • EX) 십진수에서 어떤 수 이하의 가장 큰 10의 거듭제곱을 찾을 때
    • N=650일 때 650은 세 자리 수, 가장 큰 10의 거듭제곱은 100(10^2)이다.
    • 즉 10^(3-1)=100으로 계산 가능하다. => (전체 자릿수-1)만큼 제곱하면 최대 거듭제곱수를 찾을 수 있다!
  • n.bit_length() 는 n의 비트 길이를 출력한다.
  • 1 << k 는 2^k 거듭제곱 계산을 의미한다.

            따라서  1 << (n.bit_length() - 1) 은 n 이하의 가장 큰 2의 거듭제곱 값을 출력하게 된다.