풍선 터뜨리기_2346

문제이해

• 풍선을 터뜨리고 풍선안에 있는 숫자를 확인하여 그 숫자만큼 이동한 후 다음 풍선을 터뜨린다.
• 모든 풍선이 터뜨릴때까지 위 행위를 반복한다.

예제풀이

• 처음에는 1번째 풍선부터 터뜨리므로 1을 출력, 그 후 풍선안에 3이 들어있으므로 우측으로 3만큼 이동한 후 해당 풍선의 순서인 4를 출력
• 4번째 풍선 안에는 -3이 들어있으므로, 좌측으로 3만큼 이동하고 이때 첫번째 풍선은 이미 터뜨리고 없으므로 5번째 풍선으로 이동한다.

문제풀이

• 예제풀이 두번째 줄에서 알 수 있듯이 순환적인 구조로 보았을 때 덱을 이용하여 풀어보았다.

  덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조이다.

1. 입력 받은 풍선 데이터를 덱에 저장
   • 각 풍선의 번호와 값을 덱에 저장한다.
2. 덱에서 요소를 순차적으로 제거:
   • 현재 인덱스의 풍선을 터뜨리고 그 번호를 출력한다.
   • 터진 풍선의 값을 덱에서 제거하거나 표시한다
3. 다음 인덱스로 이동
   • 양수인 경우 오른쪽으로, 음수인 경우 왼쪽으로 이동하면서, 터진 풍선을 건너뛴다.

코드

참고로 덱을 통해 구현한 코드는 해당 문제에서 메모리 초과가 난다.

이에 찾아보니 자바스크립트 자체가 메모리를 많이 잡아먹는다고 한다.

const fs = require("fs");
// 입력 파일 경로 설정
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
// 입력 데이터 읽어오기
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]); // 풍선의 개수
const values = input[1].split(" ").map(Number); // 각 풍선 안의 값

// 덱 클래스 정의
class Deque {
    constructor() {
        this.items = []; // 덱을 저장할 배열
        this.start = 0;  // 덱의 시작 인덱스
        this.end = 0;    // 덱의 끝 인덱스
    }

    // 덱의 뒤쪽에 요소 추가
    pushBack(element) {
        this.items[this.end] = element;
        this.end++;
    }

    // 덱의 앞쪽에서 요소 제거
    popFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        const item = this.items[this.start];
        this.start++;
        return item;
    }

    // 덱의 크기 반환
    size() {
        return this.end - this.start;
    }

    // 덱이 비어있는지 확인
    isEmpty() {
        return this.size() === 0;
    }

    // 덱의 앞쪽 요소 반환
    front() {
        return this.items[this.start];
    }

    // 덱의 특정 인덱스에 있는 요소 제거 (null로 표시)
    remove(index) {
        const item = this.items[index];
        this.items[index] = null;
        return item;
    }

    // 덱의 특정 인덱스에 있는 요소 반환
    get(index) {
        return this.items[index];
    }
}

// 덱 초기화
const deque = new Deque();
for (let i = 0; i < N; i++) {
    deque.pushBack([i + 1, values[i]]); // 각 풍선을 [번호, 값] 형태로 저장
}

let currentIndex = 0; // 현재 인덱스

for (let i = 0; i < N; i++) {
    // 현재 풍선을 터뜨리고 출력
    const [pos, step] = deque.get(currentIndex);
    process.stdout.write(pos.toString());
    if (i < N - 1) {
        process.stdout.write(' ');
    }
    deque.remove(currentIndex); // 현재 인덱스의 풍선을 제거 (null로 표시)

    // 터진 풍선을 건너뛰면서 step만큼 이동
    let count = Math.abs(step);
    if (step > 0) {
        // 양수일 경우 오른쪽으로 이동
        while (count > 0) {
            currentIndex = (currentIndex + 1) % N;
            if (deque.get(currentIndex) !== null) {
                count--;
            }
        }
    } else {
        // 음수일 경우 왼쪽으로 이동
        while (count > 0) {
            currentIndex = (currentIndex - 1 + N) % N;
            if (deque.get(currentIndex) !== null) {
                count--;
            }
        }
    }
}

다른 코드(파이썬)

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
# 풍선의 값을 deque로 저장, 풍선 번호와 함께 저장 (0부터 시작하는 인덱스)
q = deque(enumerate(map(int, input().split())))
# 결과를 저장할 리스트
ans = []
# deque가 빌 때까지 반복
while q:
 	# 현재 풍선의 인덱스와 값을 가져옴
    idx, paper = q.popleft()
	 # 터뜨린 풍선의 번호를 결과 리스트에 추가 (1부터 시작하는 번호)
    ans.append(idx + 1)

    # 풍선의 값에 따라 deque를 회전시킴
    if paper > 0:
        q.rotate(-(paper - 1))  # 오른쪽으로 이동 (1은 이미 이동했으므로 -1)
    elif paper < 0:
        q.rotate(-paper)  # 왼쪽으로 이동

# 결과를 공백으로 구분하여 출력
print(' '.join(map(str, ans)))

이렇게 파이썬으로 풀었더니 정상적으로 출력이 완료되었다.

자바스크립트로 코테를 하지 말까?라는 생각을 잠깐 하게된 문제였다.