[백준 코테] 2164번:카드2

 

이렇게 짜니 시간초과가 나왔다...(너무 생각없이 짜긴 했다.)

 

지금 보니 stack이 아닌 queue 형태의 코드이다.

 

좀 더 생각해보니, queue 방식을 이요해서 써야할 것 같다. 

좀 더 검색해봤다. 

 

"조세퍼스 문제(Josephus problem)"와 유사한데, 여기서는 각 단계마다 첫 번째 요소를 제거하고 두 번째 요소를 큐의 끝으로 이동시키는 과정을 반복한다. 이러한 패턴을 고려할 때, n이 주어졌을 때 마지막에 남는 요소를 직접 계산할 수 있는 수학적 공식을 적용할 수 있다. 하지만 이 경우에는 단순히 마지막에 남는 요소를 찾는 것이므로, 더 간단한 방식을 사용할 수 있다.

 

마지막에 남는 요소는 2의 거듭제곱으로 n을 초과하지 않는 최대값과 n 사이의 관계로 표현될 수 있다. 예를 들어, n=6인 경우, 22의 거듭제곱 중 66을 초과하지 않는 최대값은 4이고, 마지막에 남는 요소는 2다.. 이 관계를 이용하여 효율적인 코드를 작성할 수 있다.

 

def last_remaining(n):
    # 2의 거듭제곱 중 n을 초과하지 않는 최대값 찾기
    power_of_two = 1
    while power_of_two * 2 <= n:
        power_of_two *= 2
    
    # 마지막에 남는 요소 계산
    last = 2 * (n - power_of_two) + 1
    return last

# n 입력 받기 (예제에서는 표준 입력 대신 직접 값을 지정)
n = int(sys.stdin.readline())
print(last_remaining(n))