[Python]백준 2346 ::풍선 터뜨리기 문제 풀이

Idea.

배열 사용. (인덱스 값은 항상 가지고 있으니 빠르게 탐색 가능하다고 생각.)

 

풀이(어떻게 접근 하고 어떤 것이 중요했나?)

입력받은 리스트 외에 인덱스 리스트도 항상 같이 관리해서 결과에 처음 대로 인덱스를 담을 수 있게 한다.

풍선 속 숫자에 따라 다음 인덱스 값을 정한다.

풍선 속 숫자가 음수이면 인덱스에 풍선 속 숫자를 더한 후 리스트의 길이로 나누면 다음 인덱스가 나온다.

풍선 속 숫자가 양수이면 인덱스에 풍선 속 숫자에서 1을 뺀 것을 더한 후 리스트의 길이로 나누면 다음 인덱스가 나온다.

나온 인덱스로 갱신 하고 두 리스트 모두 pop 해서 처리한다.

리스트의 길이가 0이 될때까지 반복한다.

 

 

구현 코드

N = int(input())

list_N = list(map(int, input().split()))
list_index = []
result = []

for i in range(1,N+1):
    list_index.append(i)
    
idx = 0
k = list_N.pop(idx) # k 는 풍선 속 숫자
result.append(list_index.pop(idx))


while(len(list_N) > 0):
        
    if(k < 0):
        idx = (idx+k) % len(list_N)
    else:
        idx = (idx+(k-1))%len(list_N)
        
    k = list_N.pop(idx)
    result.append(list_index.pop(idx))
        
        
for j in range(N):
    print(result[j], end=" ")