✅ deque

문제

링크

풀이

1. 문제 접근

주어진 예제를 통해 이해를 해보면
[3 2 1 -3 -1] 의 순서대로 풍선이 있고

1. 첫번째 풍선부터 터지므로 터질 풍선은 3이고 위치는 "1"이다.
   -> [2 1 -3 -1]
   터진 곳에서부터 오른쪽으로 3만큼 이동하면

2. 다음에 터질 풍선은 -3이고 위치는 "4"이다.
   -> [2 1 -1]
   터진 곳에서부터 왼쪽으로 3만큼 이동하면

3. 다음에 터질 풍선은 -1이고 위치는 "5"이다.
   -> [2 1]
   터진 곳에서부터 왼쪽으로 1만큼 이동하면

4. 다음에 터질 풍선은 1이고 위치는 "3"이다.
   -> [2]
   터진 곳에서부터 오른쪽으로 2만큼 이동하면

5. 다음에 터질 풍선은 2이고 위치는 "2"이다.
   -> 남은 풍선이 없으므로 종료
   즉, 터진 풍선의 번호는 1 - 4 - 5 - 3 - 2

여기서 말하는 터질 풍선의 위치는 처음 순서 기준이다.

2. 자료구조 선택과 그 이유

즉, 원 형태로 데이터를 저장하여 탐색하는 문제로 queue를 통해 구현할 수 있다. 하지만 이문제는 왼쪽, 오른쪽 모두 이동 가능하기 때문에 deque를 사용한다.

3. 문제 해결 로직 (풀이법)

이전 문제와 동일하게 해당 순서가 아닌 풍선은 순번이 넘어가고
해당 순서 풍선은 제거되며 그때 처음 순서 기준으로 위치를 반환한다.

주의해야 할 점은, 처음 순서 기준으로 위치를 반환해야 하기 때문에 처음 위치도 같이 저장해야 한다.
본인은 pair<풍선에 적힌 번호, 처음 순서 기준 위치>을 사용함

의사코드

cin >> N

for(i : 1 ~ N){
	cin >> num
	que.push(make_pair(num, i))
}

// 첫번째 풍선부터 시작
vector.push(dq.front.second)
jump = dq.front.first
dq.pop_back
if(jump > 0) jump--
else jump++

while(!que.empty){
	if(jump > 0){ // 오른쪽으로 이동
    	while(jump != 0){
			dq.push_front(dq.back)
            dq.pop_back
			jump --;
        }
        vector.push(dq.back.second)
        jump = dq.back.first
        dq.pop_back
    }
    if(jump < 0){ // 왼쪽으로 이동
    	while(jump != 0){
			dq.push_back(dq.front)
            dq.pop_front
			jump ++;
        }
        vector.push(dq.front.second)
        jump = dq.front.first
        dq.pop_front
    }
}

print(vector)

4. 시간 복잡도 분석

O(N^2)

5. 문제에서 중요한 부분

문제 자체는 이전문제와 동일한 풀이 방법이지만 처음 순서를 저장해둬야 하기 때문에
구현이 약간 더 복잡함