백준 2346 : 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

 

풍선을 터뜨려서 풍선 안에 적힌 숫자만큼 이동 후 다음 풍선을 터뜨리는 문제이다.

 

첫 번째로 푼 방법은 int 자료형의 배열을 선언해 입력 값을 받고 풍선에 적힌 숫자만큼 인덱스를 이동시켜주는 방법이다.

다른 자료구조를 사용해 중간의 값을 지워가면서 인덱스를 움직이는 대신 터진 풍선은 숫자를 0으로 갱신하고 숫자가 0이 아닌 경우에만 인덱스를 이동한 횟수로 추가하여 구현하였다.

근데 풀고나서 생각해보니 결국에는 모든 풍선을 전부 터뜨려야 하기 때문에, 직접 데이터를 지우는 것이나 내가 푼 방법이나 결국 n개의 작업에 대하여 작업마다 O(n)의 시간복잡도를 가진다.

 

아래는 첫 번째 풀이 코드다.

#include <iostream>

using namespace std;

int n;
int balloon[1000];

int main() {
	int idx = 0;
	int cnt = 0;
	int remain, val;

	cin >> n;
	remain = n;

	for (int i = 0; i < n; i++) 
		cin >> balloon[i];

	//풍선이 남아있는 동안
	while (remain) {
    	//index 이동
		while (cnt != 0) {
			if (cnt > 0) val = 1;
			else val = -1;

			idx += val;

			//index 범위가 초과하는 경우
			if (idx >= n) idx -= n;
			else if (idx < 0) idx += n;

			//풍선에 적힌 숫자가 0이 아닌 경우
			if (balloon[idx]) cnt -= val;
		}

		//해당 index에 있는 풍선 터뜨리기
		cnt = balloon[idx];
		balloon[idx] = 0;
		cout << idx + 1 << ' ';
		--remain;
	}

	return 0;
}

메모리: 2024 kb

시간: 8 ms

 

보다시피 시간이 8 ms가 나왔다. 0 ms로 푼 사람들이 많아 코드를 보니 vector를 이용하여 값을 직접 지워준 풀이였다. 시간복잡도는 같을 것으로 생각되는데 왜 내 풀이가 더 느린지 모르겠다. 그래서 다른 방법으로도 풀어봤다.

 

두 번째 풀이는 삭제 시의 시간복잡도를 고려한 Linked List 자료구조를 이용한 풀이다.

vector 사용 시 인덱스를 통한 접근이 가능해 이동에 O(1), 삭제에 O(n)가 걸리고, Linked List같은 경우 선형 접근으로 이동에 O(n), 삭제에 O(1)이 걸리므로 두 풀이가 동일한 시간복잡도를 갖는다.

 

아래는 두 번째 풀이다.

#include <iostream>
#include <list>

using namespace std;

//first는 풍선에 적힌 숫자, second는 처음 index
//데이터 삭제 시 index가 변하기 때문에 초기 index를 가지고 있어야 한다.
using lpii = list<pair<int, int>>;

lpii balloon;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, tmp;
	int offset = 0;
	lpii::iterator it;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp; balloon.emplace_back(tmp, i + 1);
	}

	//Linked List를 사용하므로 index대신 iterator를 사용
	it = balloon.begin();
	while (!balloon.empty()) {
    	//iterator 이동
		while (offset != 0) {
			if (offset > 0) {
				++it;
				--offset;
				if (it == balloon.end()) it = balloon.begin();
			}
			else {
				if (it == balloon.begin()) it = balloon.end();
				--it;
				++offset;
			}
		}
		
		offset = it->first;
		//해당 위치의 데이터가 삭제되고 iterator가 다음 데이터를 가리키므로
		if (offset > 0) --offset;
		cout << it->second << ' ';

		//해당 iterator가 가리키는 데이터 삭제
		it = balloon.erase(it);
		if (it == balloon.end()) it = balloon.begin();
	}

	return 0;
}

메모리: 2152 kb

시간: 0 ms