[백준] 2346번: 풍선 터뜨리기 (실버 3) - Javascript 풀이 (시간초과)

💡 유형: 자료구조

문제 링크

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

 

풀이(시간초과)

<상황>

1. 1~N번까지 풍선 원형 배치 (시계방향)

2. 풍선 안에 번호 적힌 종이 있음 

 

<실행>

1. 1번 풍선을 터뜨린다.

2. 1번 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다.

3. 이동방향은 시계방향이고, 이미 터진 풍선은 빼고 이동한다.

 

풍선 인덱스 정보와 풍선 속 숫자 정보를 함께 저장하는 배열을 새로 생성했다.

const fs = require('fs');
const input = fs.readFileSync('예제.txt', 'utf8').trim().split('\n');

const N = parseInt(input[0]);
let balloons = input[1].split(' ').map(Number).map((val, idx) => [val, idx + 1]); // [풍선 속 숫자, 풍선 번호]
const result = [];

let index = 0; // 첫 번째 풍선부터 시작

while (balloons.length > 0) {
    let [paperNum, balloonNum] = balloons[index]; // 현재 풍선 정보 저장
    result.push(balloonNum); // 터뜨린 풍선의 원래 번호 저장

    balloons.splice(index, 1); // 풍선 제거

    if (balloons.length === 0) break; // 모든 풍선을 터뜨렸으면 종료

    // 다음 위치 계산
    if (paperNum > 0) {
        index = (index + paperNum - 1) % balloons.length; // 오른쪽 이동(현재 위치 포함하므로 -1)
    } else {
        index = (index + paperNum) % balloons.length; // 왼쪽 이동
        if (index < 0) index += balloons.length; // 음수 인덱스 보정
    }
}
console.log(result.join(' '));

 

 

 

node.js는 기본적으로 메모리를 많이 사용하므로 이런 많은 연산이 필요할 때 적은 메모리 제한을 두는 문제에 쓰는 것은 적합하지 않다.(백준에서 자바스크립트 문제를 풀기 어려운 이유ㅎㅎㅠ) 따라서 이 문제는 파이썬 등 다른 언어로 풀이하는 것이 맞지만, 나는 Javascript 로 알고리즘을 학습하는 데에 목적이 있으므로 이 풀이를 올려본다.