2346. [Python]풍선 터뜨리기

1. 문제

 

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

2346번: 풍선 터뜨리기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 4MB
• 자료 구

 

3. 파이썬 코드

 

# 풍선 갯수
N = int(input())
# 풍선에 적힌 번호
num_list = list(map(int,input().split()))
# 풍선 번호와 인덱스 저장 리스트
check_list = []

for i,v in enumerate(num_list):
    check_list.append((v,i))
# 인덱스 번호
index = 0
# 리스트 길이 저장
list_length = len(num_list)
# 체크 리스트 존재하지 않을때 까지 반복문시행
while check_list:
    # 체크 변수에 리스트 인덱스 번호 추출
    check = check_list.pop(index)
    # 리스트 값이 -1 되서 길이 -1
    list_length -= 1
    # 리스트 길이를 먼저 -1 해주기 때문에 아래 연산이 맨 마지막 값에 대해서 0으로 나누기 때문에 0이면 1 넣어줌
    if list_length == 0:
        list_length = 1
    # 추출한 값이 양수인 경우 인덱스 번호는 -1을 해줘야 함으로 -1을 한 후  기존의 index 와 더한 후 리스트 길이보다 얼마나 클지 모르기 때문에 리스트 길이의 나머지를 구해줌
    if check[0] > 0:
        index = ((check[0] - 1) + index)%list_length
    # 음수인경우 인덱스와 그냥 더한 후 리스트 길이의 나머지를 구한다
    elif check[0] < 0:
        index = (check[0] + index)%list_length
    # 같이 넣어뒀던 인덱스 번호를 출력한다.
    print(check[1]+1, end=" ")

 

4. 문제를 풀고난 후 생각

 

• 어느 풍선을 뽑았는지와 풍선을 뽑고난 후 인덱스의 위치 및 풍선의 값들이 요구되는 문제다.
• 새로운 리스트를 생성하여 들어온 풍선에 들어있는 값과 풍선의 번호를 같이 리스트 형태로 넣어서 이 리스트를 이용하여 문제를 해결한다.
• check 값이 양수일때 -1을 해주는 이유는 인덱스 값이 0부터 시작하기 때문에 고려하여 인덱스 값에 더하기 전 -1 연산을 진행 해준다.
• 리스트 길이로 나눠주는 이유는 리스트 값들이 계속해서 빠지기 때문에 현재 리스트 길이에 맞도록 인덱스 번호를 설정해 줘야 한다. 예를 들어 현재 인덱스가 10 일 경우 리스트 길이가 3 이면 3번 나뉘고 한번 더 간 1 의 인덱스에 위치 해야기 때문에 나머지 연산을 처리해준다.
• 음수의 경우는 -1 부터 시작하고 음수의 경우 나머지 처리는 값이 -1 이고 리스트 길이가 5 인 경우 4로 반환 된다.
• 이렇게 풍선을 뽑으면 그 안에 다음 인덱스 번호와 현재 풍선의 인덱스가 같이 들어있기 때문에 풍선의 번호는 마지막에 출력 해주면 된다.

어떻게 구현하는지는 생각이 났지만 직접 코드로 만드는 과정에서 풍선의 인덱스를 빼고 변하는 인덱스를 건드려서 제대로 답이 안나왔던 것 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 자료 구조