[백준/BOJ] 2346번 풍선 터뜨리기 (C/C++)

백준 온라인 저지(BOJ) 2346번 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

* 사용언어 : C언어, C++

 

1. 문제

1번부터 N번까지의 풍선이 순서대로 원형 형태로 놓여있음 (1번 → 2번 → 3번 → ... → N번 → 1번)

각 풍선 안에 들어있는 종이에 -N보다 크거나 같고, N보다 작거나 같은 정수가 적혀있음

1번 풍선을 터뜨린 후 종이에 있는 값만큼 이동하여 다음 풍선을 터뜨림 (양수는 오른쪽, 음수는 왼쪽)

풍선이 터진 순서대로 출력

 

2. 풀이

node struct를 활용하여 DEQUE(Double Ended QUEue)를 직접 구현해서 풀었습니다.

node 내부에 prev, next라는 node의 pointer 변수를 선언한 뒤 해당되는 노드의 주소로 연결하면

메모리를 과하지 않게 사용하면서 node를 연결해줄 수 있습니다. (주소값은 4 byte (32bit compiler 기준))

 

위와 같이 DEQUE를 구현하여 list 자료구조를 base로 풀 경우 각 풍선마다 최대 N회만 이동하면 되는데,

배열로 풀 경우 매 풍선마다 최대 N^2 만큼 이동해야 합니다.

(터진 풍선을 skip하면서 터지지 않은 풍선의 개수가 N이 될 때 까지 반복해서 loop를 돌아야 함)

 

풍선의 번호(idx)와 종이에 적힌 숫자(v)를 세팅해주는 과정에서

편의를 위해 0번 노드와 1001번 노드를 사용했기 때문에 N을 1002로 초기화했습니다.

(for문 종료 후에 1번과 N번만 연결해주면, 입력 받을 때 조건문으로 처리할 필요가 없음)

 

그 외 풀이는 문제 요구사항 그대로 코드로 작성했으니 아래 코드를 참고하시면 될 것 같습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2346_풍선 터뜨리기
1136KB	0ms
*/
#include <cstdio>

const int LM = 1002;
int N, k;

struct node {
	int idx, v;
	node* prev;
	node* next;
} NODE[LM];

node* cur;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		NODE[i].idx = i;
		scanf("%d", &NODE[i].v);
		NODE[i].prev = &NODE[i - 1];
		NODE[i].next = &NODE[i + 1];
		NODE[i + 1].prev = &NODE[i];
		NODE[i - 1].next = &NODE[i];
	}
	NODE[1].prev = &NODE[N];
	NODE[N].next = &NODE[1];

	cur = &NODE[1];

	while (1) {
		printf("%d ", cur->idx);
		if (cur->next == cur) break;

		cur->prev->next = cur->next;
		cur->next->prev = cur->prev;
		k = cur->v;

		if (k > 0) {
			while (k--) cur = cur->next;
		}
		else {
			while (k++) cur = cur->prev;
		}
	}
	return 0;
}