[python]2346_풍선 터뜨리기

1 걸린 시간 : 1h 30m

2 사용한 자료구조 및 개념 : list, index, %연산자

---

💡 문제풀이 아이디어 및 어려웠던 점

---

💫 아이디어

    1️⃣ 풍선의 인덱스 값과 이동 거리를 활용한다

    2️⃣ 풍선 리스트와 이동 거리 리스트를 따로 둔다

---

👻 어려웠던 점

 

🚨 list index out of range 

❓이유 

: balloon리스트에서 풍선을 제거하면서 리스트의 길이는 줄어드는데, 거기에 따른 인덱스 조정이 제대로 이루어지고 있지 않음.. 마지막 2개만 남았을 때!

n = int(input())
balloon = list(range(1, n + 1))
value = list(map(int, input().split()))
idx = 0
result = []

while balloon:
    move = balloon[idx + value[idx]]
    result.append(balloon.pop(idx))
    del value[idx]
    idx = balloon.index(move)

print(*result)

 

 ❗ 해결 시도 그러나 런타임 에러…흑흑 

: 이동 거리가 리스트의 길이를 벗어날 경우 나머지로 위치 재조정, 풍선이 다 터지면 반복문 그만! 으로 수정

그러나 테스트케이스는 통과지만 제출했을 때 런타임 에러가 발생..흑흑
나머지 연산자를 사용할 때,

-1 % 5는 4를 반환 이런 경우 음수로 이동해야하나, 음수에 대한 나머지를 항상 음수로 반환하지 않음!!

n = int(input())
balloon = list(range(1, n + 1))
value = list(map(int, input().split()))
idx = 0
result = []

while balloon:
    move = idx + value[idx]
    if move >= len(balloon):
        move %= len(balloon)
    next = balloon[move]
    result.append(balloon.pop(idx))
    del value[idx]
    if not balloon:
        break
    idx = balloon.index(next)

print(*result)

• move = idx + value[idx]라는 부분에서, value[idx]가 음수일 경우 move 값이 음수가 될 수 있음
• 이후 move %= len(balloon)에서 move는 음수를 나머지로 계산하게 되며,
  파이썬의 나머지 연산 특성으로 인해 이 값은 양수가 됨
• 따라서 이후 next = balloon[move]에서 의도치 않게 다른 위치의 풍선을 참조하게 됨

---

💡 파이썬의 나머지 연산 특성

- 파이썬에서 나머지 연산자 % 는 피연산자 중 한나가 음수일 때 특별한 동작을 함.

- 음수에 대한 나머지 연산의 결과는 항상 우항의 부호를 따름.
  그래서 결과값이 항상 0 ~ 우항 사이에 있게 됨을 보장함!

-  -1 % 3 = 2  여기서 -1을 3으로 나누면 -0.33… 임

  이 때 몫은 0에 가까운 방향으로 반올림 되므로 -1이 됨

  나머지를 계산하는 방법은 (원래 수) - (나눈 수 * 몫) 임 따라서 이 경우 -1 - (3 * -1) = 2 가 되는 것

 

 

❗찐해결
: move 가 음수일 경우와 양수일 경우를 분리하여 계산~! (아래 코드 참고)

---

Solution Code & 주석

n = int(input())
balloon = list(range(1, n + 1))
value = list(map(int, input().split()))
idx = 0
result = []

while balloon:
    move = value[idx]
    result.append(balloon.pop(idx))
    del value[idx]
    if not balloon:
        break
    if move > 0:
        move -= 1
    idx = (idx + move) % len(balloon)

print(*result)

✔️ move -= 1 을 하는 까닭은 풍선이 터져서 사라지면 리스트에서 인덱스가 하나 줄어듦.

     양수의 경우에는 기존 위치에서 오른쪽으로 이동하려면 터진 풍선의 위치를 고려해야함.

     음수의 경우에는 왼쪽으로 이동하므로 터진 풍선의 위치를 고려하지 않아도 됨!