[Python] 백준, 2164(큐)

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

2164번: 카드2

단순함 속에서도 배울 건 존재하기 마련이다. 문제 자체는 굉장히 단순하지만, 어째서인지 deque가 아닌 리스트로 접근하면 시간 초과가 발생한다. 풀이 자체에 큰 어려움을 느끼지는 않았지만 소개할 두 번째 풀이가 조금 감명 깊었다. 알고리즘에 수학이 필연적인 이유를 어렴풋이 느끼게 되었달까... 

 

 

 

# PYTHON CODE (1) - 리스트 매서드 실패

n = int(input())
 
d = [i + 1 for i in range(n)][::-1]
 
while len(d) != 1:
    d.pop()
    d = [d.pop()] + d
 
print(d[0])

# PYTHON CODE (2) - deque 모듈

from collections import deque
 
n = int(input())
d = deque([i + 1 for i in range(n)])
 
while len(d) != 1:
    d.popleft()
    d.append(d.popleft())
    
print(d[0])

# PYTHON CODE (3) 

n = int(input())
count = 2
 
if n == 1 or n == 2:
    print(n)
 
else:
    while True:
        count *= 2
        if count >= n:
            print((n - (count // 2)) * 2)
            break

이 풀이에 대한 스케치 먼저 소개하는 게 좋을 거 같다.

 

위에서 볼 수 있듯이, input에 일정한 값들을 대입하여 output을 관찰하면 일정한 규칙을 발견할 수 있는데, 이를 이용하여 알고리즘을 짜는 것이 세 번째 코드이다. 주목할 부분은 2의 제곱수인 부분에서의 처리가 까다롭다는 건데, 위 사진의 풀이1을 참고하면 쉽게 이해할 수 있을 것 같다.

 

2164번 맞은 사람 풀이에서 무려 3위에 랭크되었다. 다른 사람들의 생각을 캐치해서 좀더 개선한 것이라서 조금 아쉽긴 하지만 이런 식의 풀이에 대한 접근도 좋은 것 같다.