[백준/Python] 2346 풍선 터뜨리기

문제링크

2346번: 풍선 터뜨리기

 

문제풀이

자바스크립트로 풀다가 메모리가 계속 터져서 아마 deque을 구현해야할텐데, 실제 코테에서 그러고 있으면 광탈 확정이기 때문에 파이썬으로 풀었습니다.

 

자바스크립트도 로직은 맞을겁니다. 진짜로요.

const fs = require("fs");

BOJkey = 0;

let input = fs
  .readFileSync(BOJkey ? "./자바스크립트로/2346/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n");

let num = +input[0];
let arr = input[1].split(" ").map((v) => +v);
let deque = [];
let count = 1;
let balloonCount = 1;
let dequeCheck = true; // true가 앞 false가 뒤
let result = [];
// console.log(arr);
let target;
for (let i = 1; i <= num; i++) {
  deque.push([i, arr[i - 1]]);
}
while (deque.length) {
  if (Math.abs(balloonCount) == count) {
    if (dequeCheck) target = deque.shift();
    else target = deque.pop();
    if (target[1] > 0) dequeCheck = true;
    else dequeCheck = false;
    balloonCount = target[1];
    result.push(target[0]);
    count = 1;
  } else {
    if (dequeCheck) {
      target = deque.shift();
      deque.push(target);
      count++;
    } else {
      target = deque.pop();
      deque.unshift(target);
      count++;
    }
  }
}
console.log(result.join(" "));

 

그래서 위 코드를 파이썬으로 바꿔서 풀었더니 정답이였습니다.

이 문제는 deque 문제이고 어떻게 좌우로 풍선을 움직일 것인가? 에 대한 고민을 했습니다.

좌우 모두를 사용할 수 있는 자료구조여야했기때문에 queue 보다는 deque 이 맞을 것이라고 생각했습니다.

문제 아이디어는 다음과 같습니다.

 

count = 풍선을 이동시킨 횟수

balloonCount = 풍선에 들어있던 숫자

dequeCheck = 덱을 앞으로 쓸건지 뒤로 쓸건지 판단 ( 저는 true 일때는 앞, false 일때는 뒤 ) 라고 생각했습니다.

result = 정답을 저장하는 배열

 

처음 시작하는 경우에는 무조건 앞에서 pop 해야하기때문에 count = 1, balloonCount =1 로 두어서 바로 실행될 수 있도록 했습니다. 또한 dequeCheck = True 입니다 앞에서 시작해야하기 때문이죠.

 

dequeCheck 이 true 이냐 false 이냐에 따라 앞뒤 팝을 결정하게 되고

풍선안에 들어있던 숫자가 양수이면 계속 앞을 pop 하면 되고 숫자가 음수이면 뒤에서 pop을 해주어야합니다.

왜 그런지는 그림을 그리면서 시뮬레이션을 하다보니까 저런 생각을 하게되었습니다.

 

balloonCount 와 count가 같지 않을 경우에는 dequeCheck 에 따라 앞을 pop 했다면 뒤에 append를 해주는 방식으로 환영 큐 처럼 생각을 했습니다.

반대도 마찬가지입니다.

from collections import deque

num = int(input())
arr = list(map(int,input().split(" ")))

deq = deque()
count = 1
balloonCount = 1
dequeCheck = True
result = []

for i in range(1,num+1) :
    deq.append([i,arr[i-1]])

while deq :
    if abs(balloonCount) ==  count :
        if dequeCheck :
            target = deq.popleft()
        else :
            target = deq.pop()
        if target[1] > 0 :
            dequeCheck = True
        else :
            dequeCheck = False
        balloonCount = target[1]
        result.append(target[0])
        count = 1
    else :
        if dequeCheck :
            target = deq.popleft()
            deq.append(target)
            count +=1
        else :
            target = deq.pop()
            deq.appendleft(target)
            count +=1

# print(result)
print(" ".join(map(str,result)))