[백준 / C언어] Day20. 풍선 터뜨리기 (2346)

2024. 06. 06 - 코딩테스트 스터디 Day20

 

 

01. 문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

 

 

02. 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

 

 

03. 출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

 

04-1. 예제 입력 1

5
3 2 1 -3 -1

 

 

04-2. 예제 출력 1

1 4 5 3 2

 

 

 

05. 풀이 및 답

원래 반복문을 돌면서 배열의 요소를 하나하나 검사하는 코드를 작성했었는데 아무리 코드를 수정해도 시간 초과 문제를 해결할 수 없어서 과감히 새로운 방법으로 시도해 보았다.

새롭게 시도해 본 방법은 '이중 원형 연결 리스트'를 사용한 방식이다.

 

 

코드 전문

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value; // 풍선 속 종이에 적힌 숫자
    int index; // 풍선의 인덱스
    struct Node *next;
    struct Node *prev;
} Node;

int main() {
    int n;
    scanf("%d", &n);
    
    Node *nodes = (Node *)malloc(sizeof(Node) * n);
    Node *head = NULL; // 처음 노드
    Node *tail = NULL; // 마지막 노드
    
    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        nodes[i].value = value;
        nodes[i].index = i + 1;
        nodes[i].next = NULL; // nodes[i].next는 현재 노드의 다음 노드를 가리킴
        nodes[i].prev = tail; // nodes[i].prev는 현재 노드의 이전 노드를 가리킴
        
        if (tail != NULL) { // 만약 이전 노드가 존재하면
            tail->next = &nodes[i]; // 그 이전 노드의 next를 현재 노드로 설정
        }
        tail = &nodes[i]; // tail을 현재 노드로 설정
        
        if (head == NULL) { // 만약 리스트의 첫 번째 노드라면 
            head = &nodes[i]; // head를 현재 노드로 설정
        }
    }
    
    // 원형 링크드 리스트로 연결
    head->prev = tail; 
    tail->next = head;
    
    Node *current = head;
    for (int i = 0; i < n; i++) {
        printf("%d ", current->index); // 현재 노드의 인덱스 번호 출력 (터짐)
        int steps = current->value;
        
        // 현재 노드를 리스트에서 제거
        current->prev->next = current->next;
        current->next->prev = current->prev;
        
        if (steps > 0) {
            for (int j = 0; j < steps; j++) {
                current = current->next;
            }
        } else {
            for (int j = 0; j < -steps; j++) {
                current = current->prev;
            }
        }
    }
    
    free(nodes);
    return 0;
}

이번 문제도 그림을 그려 이해해 보았다.

 

 

1. 노드 초기화 및 연결

    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        nodes[i].value = value;
        nodes[i].index = i + 1;
        nodes[i].next = NULL; // nodes[i].next는 현재 노드의 다음 노드를 가리킴
        nodes[i].prev = tail; // nodes[i].prev는 현재 노드의 이전 노드를 가리킴
        
        if (tail != NULL) { // 만약 이전 노드가 존재하면
            tail->next = &nodes[i]; // 그 이전 노드의 next를 현재 노드로 설정
        }
        tail = &nodes[i]; // tail을 현재 노드로 설정
        
        if (head == NULL) { // 만약 리스트의 첫 번째 노드라면 
            head = &nodes[i]; // head를 현재 노드로 설정
        }
    }

 

우선 i가 0일 때, 

nodes [0].value에 입력받은 value 값, 즉 풍선 속 종이에 적힌 숫자 값을 저장해 준다.

nodes [0].index에 i + 1인 1을 저장한다.

nodes [0].next는 우선 null로 설정해 주고,

nodes[0].prev은 tail로 설정하는데, 현재 tail도 null로 설정되어 있으므로 역시나 null이다.

 

tail이 null이므로 if문은 건너뛰고, tail을 현재 노드로 설정해 준다.

head가 null이므로 head를 현재 노드로 설정해 준다.

 

i가 1일 때,

초기화 작업은 위와 동일하게 진행한다.

 

tail이 null이 아니므로 tail, 즉 nodes[0].next를 현재 노드 nodes[1]로 설정해 준다.

tail을 현재 노드 nodes[1]로 설정해 준다.

 

위와 같은 과정을 i가 n보다 작은 동안 반복하면 위 그림과 같은 구조가 된다.

 

2. 원형 리스트로 연결

    // 원형 링크드 리스트로 연결
    head->prev = tail; 
    tail->next = head;

리스트의 첫 번째 노드인 head의 이전 노드를 마지막 노드인 tail로 설정한다.

리스트의 마지막 노드인 tail의 다음 노드를 첫 번째 노드인 head로 설정한다.

이렇게 하고 나면 이중 원형 연결 리스트의 형태를 가지게 된다.

 

정답!!

 

 

---

 

힘들닷