07.03. 풍선 터뜨리기 [Linked List][백준 2346]

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

2346번: 풍선 터뜨리기

 

Algorithm classification : Linked List, Data Structure, Deque

 

07.03.1. Problem

N balloons from 1 to N are placed in a circle. To the right of balloon i is balloon i+1, and to the left is balloon i-1. However, balloon N is to the left of balloon 1, and balloon 1 is to the right of balloon N. Each balloon contains a piece of paper, and the paper contains an integer greater than or equal to -N and less than or equal to N. Pop these balloons with the following rules:

First of all, in the first place, balloon number 1 is popped. Next, take out the paper in the balloon and move it by the value written on the paper to pop the next balloon. A positive number moves to the right, and a negative number moves to the left. When moving, remove the already popped balloon and move.

For example, suppose that 3, 2, 1, -3, and -1 are written in five balloons. In this case, balloon 1 with 3 is written on it, balloon 4 with -3 written on it, balloon 5 with -1 written on it, balloon 3 with 1 written on it, and balloon 2 with 2 written on it will burst in that order.

 

07.03.2. Input limit

A natural number N (1 ≤ N ≤ 1,000) is given in the first line. The next line is given the number written on the paper inside each balloon in turn. There is no zero written on the paper.

 

07.03.3. Output

In the first line, list the numbers of the popped balloons in order.

 

07.03.4. Solution

문제 난이도가 실버라서 그런지 시간이 넉넉합니다.(아주 편안하네요.) Vector로도 풀어보시고 원형 이중 연결 리스트로도 풀어보면 좋을 것 같습니다. 이쯤되면 code 돌려막기가 가능해지는군요.

typedef struct node{
	int index;
	int data;
	struct node* next;
	struct node* prev;
}NODE;

typedef struct list{
	NODE* head;
	int size;
}LIST;

void insert(LIST* l, int data);
void remove(LIST* l);

 

node 삽입은 이전 문제들과 유사합니다.

void insert(LIST* l, int data){
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->data = data;
	newNode->next = newNode->prev = newNode;
	newNode->index = l->size + 1;
	
	if(l->head == NULL){
		l->head = newNode;
	}
	else{
		NODE* curNode = l->head;
		for(int i = 1; i < l->size; i++){
			curNode = curNode->next;
		}
		curNode->next = newNode;
		newNode->prev = curNode;
		l->head->prev = newNode;
		newNode->next = l->head;
	}
	l->size++;
	
}

 

node 삭제에 몇줄만 조금 더 추가해주시면 되겠군요. 중간에 헷갈리시거나 검증이 필요한 부분은 제가 주석처리해 놓은 것처럼 중간에 찍어보시면 됩니다.

void remove(LIST* l){
	NODE* removeNode = l->head;
	int move = l->head->data;
	
	printf("%d ", l->head->index);
	//printf(": %d", l->head->data);
	if(l->size == 1){
		l->size--;
		return;
	}
	
	if(move > 0){
		for(int i = 0; i < move; i++){
			l->head = l->head->next;
			if(l->head == removeNode){
				l->head = l->head->next;
			}
			//printf("/%d %d %d", l->head->index, l->head->prev->index, l->head->next->index);
		}
	}
	else{
		for(int i = 0; i < move * -1; i++){
			l->head = l->head->prev;
			if(l->head == removeNode){
				l->head = l->head->prev;
			}
			//printf("/%d %d %d", l->head->index, l->head->prev->index, l->head->next->index);
		}
	}
	//printf("/%d %d %d/", l->head->index, l->head->next->index, l->head->prev->index);
	removeNode->next->prev = removeNode->prev;
	removeNode->prev->next = removeNode->next;
	//printf("%d %d %d/", removeNode->index, removeNode->next->index, removeNode->prev->index);
	//printf("%d %d %d\n", l->head->index, l->head->next->index, l->head->prev->index);
	free(removeNode);
	l->size--;
}

 

destroy list function을 별도로 만들진 않았지만 main function 마지막에 list를 free해주어야 합니다.

 

하나의 test case를 남겨두겠습니다.

5
-5 -5 -5 -5 -5
>> 1 5 3 2 4