백준_2346_풍선 터뜨리기(python)

※ 접근

처음에 N의 개수를 보고 완전탐색을 해도 되겠구나 싶었고 문제를 읽고 큐를 사용했다. 하지만 인덱스 움직이는 것에 제한이 있었고 큐를 사용하면 안된다는 것을 느껴 덱으로 생각을 전환해 접근했다.

 

※ 풀이

입력을 받을 때 수열로 입력받고 하나씩 꺼내어 인덱스는 +1 해서 정답 리스트에 저장하고 종이에 나온 숫자만큼 로테이트 함수를 이용해 돌려준다.

 

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

n = int(input())
q = deque(enumerate(map(int,input().split())))
ans = []

while q:
    idx,paper = q.popleft()
    ans.append(idx+1)

    if paper > 0:
        q.rotate(-(paper-1))
    elif paper < 0:
        q.rotate(-paper)
print(*ans)

※ 회고

 처음에 문제를 딱 봤을 때 요세푸스 문제인 줄 알았다. 그래서 idx를 어떻게 움직일지를 계속 고민했다. 몇 시간을 쏟았지만 아이디어가 떠오르지 않아 요세푸스가 아닌가 싶어 알고리즘 힌트를 봤다 덱이란 것을 보고 깨달았다.

 다음부터 고정관념에 깊게 휩쓸리지 말고 다른 생각도 직관적으로 해봐야 할 것 같다.