[백준] 2346 - 풍선 터트리기

🖥️ 시작하며

파이썬의 풀이는 인터넷에 많이 있다. deque 의 rotate 를 사용한 방법으로, 직관적이고 보기 쉽다.

C언어는 좀 다른 방법으로 해결했다.


// 풍선 초기화
for (int i = 1; i <= N; ++i) {
    balloons[i].idx = i;
    scanf("%d", &balloons[i].value);
    balloons[i].popped = 0;
    balloons[i].prev = (i == 1) ? N : i - 1;
    balloons[i].next = (i == N) ? 1 : i + 1;
}

순서대로 입력받은 풍선을 저장했다. prev 와 next 를 통해 다음 풍선이 어디인지 정해지도록 했다.


int current = 1; // 첫 번째 풍선부터 시작

for (int count = 0; count < N; ++count) {
    printf("%d ", balloons[current].idx);
    balloons[current].popped = 1; // 현재 풍선을 터뜨림

    if (count == N - 1)
        break; // 마지막 풍선이면 종료

    int move = balloons[current].value;

    // 현재 풍선을 리스트에서 제거
    int prev = balloons[current].prev;
    int next = balloons[current].next;
    balloons[prev].next = next;
    balloons[next].prev = prev;

    // 이동할 방향에 따라 다음 풍선으로 이동
    if (move > 0) {
        // 오른쪽으로 이동
        for (int i = 0; i < move; ++i) {
            current = balloons[current].next;
        }
    } else {
        // 왼쪽으로 이동
        for (int i = 0; i < -move; ++i) {
            current = balloons[current].prev;
        }
    }
}

첫 번째 풍선을 터트리고 출력한다.

만약 마지막 풍선이면 종료시킨다.

해당 풍선의 값(다음 인덱스)를 move 에 저장한다.

현재 풍선을 리스트에서 제거한다. 간단하게 이전, 이후의 풍선의 이전, 이후를 바꿔주면 된다.

move 에 따라 다음 풍선으로 이동하고, 이전 과정을 반복한다.

⚙️ 코드


from collections import deque


def Solution(queue):
    result = []

    # 첫 번째 풍선
    cur_index, move = queue.popleft()  # pop(0)과 같음
    result.append(cur_index)

    # 풍선이 남아 있는 동안 반복
    while queue:
        if move > 0:
            queue.rotate(
                -(move - 1)
            )  # 이미 한 번 터뜨렸으므로 회전된 상태이니 move - 1만큼 회전
        else:
            # 음수일 때는 왼쪽으로
            queue.rotate(-move)

        # 다음 풍선 터뜨리기
        cur_index, move = queue.popleft()
        result.append(cur_index)

    return result


if __name__ == "__main__":

    # 입력 받기
    N = int(input())
    balloons = list(map(int, input().split()))

    # 인덱스와 함께 저장
    queue = deque(enumerate(balloons, start=1))

    print(" ".join(map(str, Solution(queue))))


#include <stdio.h>

#define MAX 1000

typedef struct {
    int idx;    // 풍선의 원래 인덱스
    int value;  // 풍선 안에 적힌 수
    int prev;   // 이전 풍선의 인덱스
    int next;   // 다음 풍선의 인덱스
    int popped; // 풍선이 터졌는지 여부 (0: 터지지 않음, 1: 터짐)
} Balloon;

void Solution(Balloon *balloons, int N) {
    // 풍선 초기화
    for (int i = 1; i <= N; ++i) {
        balloons[i].idx = i;
        scanf("%d", &balloons[i].value);
        balloons[i].popped = 0;
        balloons[i].prev = (i == 1) ? N : i - 1;
        balloons[i].next = (i == N) ? 1 : i + 1;
    }

    int current = 1; // 첫 번째 풍선부터 시작

    for (int count = 0; count < N; ++count) {
        printf("%d ", balloons[current].idx);
        balloons[current].popped = 1; // 현재 풍선을 터뜨림

        if (count == N - 1)
            break; // 마지막 풍선이면 종료

        int move = balloons[current].value;

        // 현재 풍선을 리스트에서 제거
        int prev = balloons[current].prev;
        int next = balloons[current].next;
        balloons[prev].next = next;
        balloons[next].prev = prev;

        // 이동할 방향에 따라 다음 풍선으로 이동
        if (move > 0) {
            // 오른쪽으로 이동
            for (int i = 0; i < move; ++i) {
                current = balloons[current].next;
            }
        } else {
            // 왼쪽으로 이동
            for (int i = 0; i < -move; ++i) {
                current = balloons[current].prev;
            }
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);

    Balloon balloons[MAX + 1];

    Solution(balloons, N);

    return 0;
}

[백준] 2346 - 풍선 터트리기

🖥️ 시작하며

⚙️ 코드

📌 소감

댓글