[210325][백준/BOJ] 2346번 풍선 터뜨리기

문제

입출력

풀이

deque를 사용하였으며 각 정수의 인덱스까지 저장하기 위해 STL pair를 사용하였다.

1. deque의 맨 앞의 인덱스를 출력하고 이를 삭제한다.
2. 원소가 양수이면 맨 앞의 값을 맨 뒤로 삽입하였고 음수이면 맨 뒤의 값을 맨 앞으로 삽입한다.
3. deque가 빌 때 까지 반복한다.

또 반복문 탈출 조건을 deque가 비어있을때( while(!DQ.empty()) )로 설정하면 반복문이 돌면서 마지막에 남아있는 원소를 pop하고 나서도 조건문이 실행되므로 정답은 정상적으로 출력되고 백준도 통과는 되지만 사진과 같은 메세지가 발생하게 된다. 따라서 반복문은 무한루프로 만들고 종료조건을 따로 적어둬서 에러 메세지를 발생하지 않게 하였다.

코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	int n;
	cin >> n;
	deque<pair<int, int>> DQ;

	for (int i = 1; i <= n; ++i)
	{
		int m;
		cin >> m;
		DQ.push_back(make_pair(i, m));
	}
	while (true)
	{
		cout << DQ.front().first << ' ';
		int idx = DQ.front().second;
		DQ.pop_front();

		if (DQ.empty())
			break;
		
		if (idx >= 0)
		{
			for (int i = 0; i < idx - 1; ++i)
			{
				DQ.push_back(DQ.front());
				DQ.pop_front();
			}
		}
		else
		{
			for (int i = 0; i > idx; --i)
			{
				DQ.push_front(DQ.back());
				DQ.pop_back();
			}
		}
	}
	/*
		-- 1 4 5 3 2 --
		 3 2 1 -3 -1   3
		-3 -1 2 1     -3
		-1 2 1        -1
		 1 2           1
		 2             2
	*/
}

느낀점

잘 안풀리던 문제가 deque를 배우고나서 deque로 다시 푸니까 풀렸다.
이 문제도 어떻게 접근하면 좋을지 생각은했지만 구현하는데 꽤 시간이 소모되었으며
백준 1021번 회전하는 큐 문제를 풀고나서 이를 이용해 문제를 해결할 수 있었다.

이처럼 여러가지 문제를 풀다보면 내 나름대로 어떻게 접근할지 방법이 보이면서 문제를 해결할 수 있을거 같다.