백준 2346

백준 2346 : 풍선 터뜨리기

1. deque 이용, deque<pair<index, value>> dq;

2. 터뜨리고

3. 숫자를 확인
   3-1. 숫자가 양수라면, (숫자-1) 만큼 앞에서 pop, 뒤에서 push
   3-2. 숫자가 음수라면, (숫자의 절대값) 만큼 뒤에서 pop, 앞에서 push

4. 맨 앞의 수가 다음으로 터트릴 수

5. 3-1의 경우에는 deque 연산만큼 idx를 증가, 3-2의 경우에는 deque 연산만큼 idx를 감소시키면 됨

6. 4번 수행 전에 매번 현재의 idx 값을 출력

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int n;
deque<pair<int, int>> dq; //{index, value}
int idx, val, temp_idx, temp_val;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n;
	for(int i=0; i<n; i++) {
		int in;
		cin>>in;
		dq.push_back({i+1, in});
	}
	
	while(dq.size()) {
		tie(idx, val) = dq.front(); //맨 앞의 값을 추출  
		dq.pop_front(); //풍선 터트리기 
		cout<<idx<<' ';
		
		if(val>0) { //수가 양수일 경우 
			for(int i=0; i<val-1; i++) {
				tie(temp_idx, temp_val) = dq.front();
				dq.pop_front();
				
				dq.push_back({temp_idx, temp_val});
			}
		}
		else { //수가 음수일 경우  
			val*=-1; //make positive
			for(int i=0; i<val; i++) {
				tie(temp_idx, temp_val) = dq.back();
				dq.pop_back();
				
				dq.push_front({temp_idx, temp_val});
			}
		}
	}
	
	return 0;
}

메모리 초과가 났다..

-> 불필요하게 너무 많이 반복해서 그러는듯: 횟수를 최소한으로

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int n;
deque<pair<int, int>> dq; //{index, value}
int idx, val, temp_idx, temp_val;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n;
	for(int i=0; i<n; i++) {
		int in;
		cin>>in;
		dq.push_back({i+1, in});
	}
	
	while(dq.size()) {
		tie(idx, val) = dq.front(); //맨 앞의 값을 추출  
		dq.pop_front(); //풍선 터트리기 
		cout<<idx<<' ';
			
		int len = dq.size();
		if(len==0) {
			len=1;
		}
		if(val>0) { //수가 양수일 경우 
			for(int i=0; i<(val-1)%len; i++) {
				tie(temp_idx, temp_val) = dq.front();
				dq.pop_front();
				
				dq.push_back({temp_idx, temp_val});
			}
		}
		else { //수가 음수일 경우  
			val*=-1; //make positive
			for(int i=0; i<val%len; i++) {
				tie(temp_idx, temp_val) = dq.back();
				dq.pop_back();
				
				dq.push_front({temp_idx, temp_val});
			}
		}
	}
	
	return 0;
}

이 부분을 추가해줬음!!!!

int len = dq.size();
if(len==0) {
	len=1;
}