[백준/Baekjoon] 2346 풍선 터뜨리기 C++/Python :: Date Structure

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

2346번: 풍선 터뜨리기

---

1. Logic

C++로 풀이할 때는 좌우로 큐를 회전시켜야 할 때 직접 빼고 넣어줘야 하기 때문에 움직여야 할 숫자가 음수인지 양수인지에 따라 경우를 나눠서 풀이했다.

하지만 파이썬으로 풀이할 때는 파이썬 queue에는 rotate라는 함수가 있기 때문에 훨씬 쉽게 구현할 수 있었다.

rotate 함수는 안에 들어가는 인자가 양수이면 큐 안의 인자들을 오른쪽으로 절댓값만큼 이동하고, 음수이면 왼쪽으로 절댓값만큼 이동시키는 함수이다. 아래의 예시를 보자

[1, 2, 3, 4, 5]가 queue에 들어가있을 때 

rotate(-2의 결과) : [3, 4, 5, 1, 2]

rotate(2의 결과) : [4, 5, 1, 2, 3]

이렇게 나오게 된다.

728x90

---

2. Code

C++

#include<bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    
    deque<pair<int, int>> dq;
    
    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        dq.push_back({a, i});
    }
    
    int cur = dq.front().first;
    cout << dq.front().second << ' ';
    dq.pop_front();
    
    while(!dq.empty()) {
        if(cur > 0) {
            for(int i = 0; i < abs(cur)-1; i++) {
                dq.push_back(dq.front());
                dq.pop_front();
            }
            cout << dq.front().second << ' ';
            cur = dq.front().first;
            dq.pop_front();
        }
        else {
            for(int i = 0; i < abs(cur)-1; i++) {
                dq.push_front(dq.back());
                dq.pop_back();
            }
            cout << dq.back().second << ' ';
            cur = dq.back().first;
            dq.pop_back();
        }
    }
}

Python

from collections import deque

n = int(input())
arr = list(map(int, input().split()))
dq = deque()

for i in range(n):
    dq.append((arr[i], i+1))

while dq:
    cur, idx = dq.popleft()
    print(idx, end= " ")
    
    if cur > 0:
        cur -= 1
    dq.rotate(-cur)

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐