[백준][C++]2346번. 풍선 터뜨리기

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

 

풍선이 원형으로 놓여져있고 왼쪽,오른쪽으로 둘다 이동할 수 있기 때문에 deque자료형을 활용해보았다.

deque자료형과 pair 자료형을 활용하여 풍선의 인덱스 풍선종이에 적힌 숫자를 매치시켜주었다.

만약 오른쪽으로이동한다면 앞에꺼를 뒤에 넣어주고 앞에꺼는 빼주면 된다.

만약 왼쪽으로 이동한다면 뒤에꺼를  앞에 넣어주고 뒤에꺼는 빼주면 된다.

이 과정을 통하여 나온 인덱스값을 정답 vector에 넣어주고 이를 출력해주면 된다.

 

이때 불필요한 이동을 줄이기 위하여 나눗셈을 사용해줄 수 있다. 

 

정답코드

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

vector<int> answer;
int main()
{
	int n, tmp = 0;

	cin >> n;

	deque<pair<int, int>> balloons; 

	for (int i = 0; i < n; i++) 
	{
		int value;
		cin >> value;
		balloons.push_back({ i + 1, value }); // 풍선 번호 / 종이에 적힌 값
	}


	while (!balloons.empty())
	{
		auto current = balloons.front();
		balloons.pop_front();
		answer.push_back(current.first);

		if (balloons.empty()) break;

		int steps = current.second;

		if (steps > 0)
		{
			for (int i = 0; i < steps - 1; i++) { // 오른쪽으로 이동
				balloons.push_back(balloons.front());
				balloons.pop_front();
			}
		}
		else
		{
			for (int i = 0; i < -steps; i++) { // 왼쪽으로 이동
				balloons.push_front(balloons.back());
				balloons.pop_back();
			}
		}
	}

	for (int i = 0; i < answer.size(); i++) {
		if (i != 0) cout << " ";
		cout << answer[i];
	}

	return 0;

}

 

 

정답코드2(나눗셈연산을 통해 이동최적화)

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    deque<pair<int, int>> balloons;

    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        balloons.push_back({i + 1, value});  // 풍선 번호와 적힌 값을 저장
    }

    vector<int> result;

    while (!balloons.empty()) {
        auto current = balloons.front();
        result.push_back(current.first);  // 풍선 번호 저장
        balloons.pop_front();

        if (balloons.empty()) break;

        int steps = current.second;

        if (steps > 0) {
            steps = (steps - 1) % balloons.size();  // 오른쪽으로 이동, 크기 안에서 회전
        } else {
            steps = steps % balloons.size();  // 왼쪽으로 이동
        }

        if (steps > 0) {  // 오른쪽 이동
            for (int i = 0; i < steps; i++) {
                balloons.push_back(balloons.front());
                balloons.pop_front();
            }
        } else if (steps < 0) {  // 왼쪽 이동
            for (int i = 0; i < -steps; i++) {
                balloons.push_front(balloons.back());
                balloons.pop_back();
            }
        }
    }

    for (int i = 0; i < result.size(); i++) {
        if (i != 0) cout << " ";
        cout << result[i];
    }

    return 0;
}