백준, BOJ, 2346번, 풍선 터뜨리기 C++ [CPP] ★★★★★

큐 같지만

덱인 문제다.

(원형큐 문제다)

꽤 생각해볼만한 문제다.

왜냐면 front가 항상 앞을 가리키고 있다고 생각하면

역방향 회전과 정방향 회전의 느낌이 조금 다른 느낌이라서 그렇다.

 

 

메모리 제한이 있기 때문에 잘 해야한다.

하나로 묶을 수 있는 것은 하나로 묶어야한다.

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

 

---

 

#내 풀이

#include <bits/stdc++.h>

using namespace std;

int N;

//메모리 제한 4MB
//int 1개 4바이트.. 256개면 1KB, 256*1024개면 1MB..?

int main(){
    
    cin >> N;
    deque<pair<int,int>> balloon;
    
    for(int i = 1; i<=N; i++){
        int x;
        cin >> x;
        balloon.push_back({i,x}); //1~N번
    }
    
    while(!balloon.empty()){
        auto cur = balloon.front(); //풍선 번호
        cout << cur.first << ' ';
        int nowNum = cur.second; //풍선 안의 숫자.
        balloon.pop_front(); //풍선 터뜨리기.

        //양수,음수
        if(nowNum > 0){
            nowNum--; // 정방향이면 -> 터뜨린 것 자체가 front를 바꾸는 행위
            while(!nowNum == 0){
                balloon.push_back(balloon.front());
                balloon.pop_front();
                nowNum--;
            }
        }else{
            //역방향이면 풍선을 터뜨려도 역방향이 front를 가리켜야하기 때문에 영향 x
            while(!nowNum == 0){
                balloon.push_front(balloon.back());
                balloon.pop_back();
                nowNum++;
            }
        }
    }
    
    return 0;
}

 

저기 nowNum 에서 왜 while 문 전이 다른가 생각해보자

1 2 3 4 5 : 풍선 번호

3 2 1 -3 -1 : 풍선 안의 종이 숫자

1 2 3 4 5 : 큐 상태

 

처음에 첫번째 풍선을 터뜨리면 큐는 이렇게 된다.

2 3 4 5 : 큐 상태

 

숫자는 3이 써있었으니. 이전 큐의 상태인 1 -> 2 -> 3 -> 4 5 에서 3번 움직이는 것이다.

즉, 움직이는 것은 풍선을 터뜨렸지만 풍선이 터진 위치에서 3번 움직여야 한다.

 

결국 큐 상태는

4 5 2 3 이 된다.

 

그 다음 4번을 터뜨린다.

5 2 3 이 된다.

4번에 적힌 숫자는 -3 이다. 마찬가지로 풍선이 터진 위치에서 역방향으로 3번 움직여야 한다.

 

(5) <- (2) <- (3) <- 4 5 2 3 상태여야 하고 3번을 역방향으로 움직여 5가 맨 앞으로 와야한다.

** 괄호는 원형큐의 모습을 담은 것이다.

 

4를 터뜨려서 뺐다면

5 2 3 으로 남아있기 때문에 

5 2 3 -> 2 3 5 ->  3 2 5 -> 5 2 3  3번의 작업이 필요한 것이다.

 

즉, 풍선이 터뜨린 것 자체가 front 위치를 바꾸는 행위인데

풍선을 터뜨려서 바뀐 front 부터 x-1번 하는 건 정방향

풍선을 터뜨려서 바뀐 front 부터 x번 하는것은 정방향

이라는 것이다.

 

??? 아니 그게 맞나..? 뭔가 이해가 안되는데??

 

 

원형 큐에 head와 tail이 있다고 생각하면 된다.

원형큐의 head에서 원소가 사라진다고 해서 tail의 위치는 변하지 않으니까 !!! head만 가리키는 것이 바뀐 것 뿐이다.

1(h) 2 3 4 5(t)

헤드를 4로 옮기고 1 제거

->

2 3 4(h) 5(t)

-> 헤드를 5로 옮기고 4제거

2 3 5(h,t)

->헤드를 3으로 옮기고 5 제거 tail이 제거되었으므로 2가 tail

2(t) 3(h)

...

이런 식이다.

 

 

다시 말해서 풍선을 터뜨리는 행위가 큐의 head를 바꾸는 행위라고 생각하면 된다.