[백준/Baekjoon] 1021 회전하는 큐 C++ :: Data structure

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

1021번: 회전하는 큐

---

1. Logic

- 문제의 조건에 따라 왼쪽에서도 값을 넣고 오른쪽에서도 값을 넣다 뺏다하기 쉬운 자료구조는 deque가 적절하다.

연산을 최소로 하기 위해서는 구해야하는 수를 기준으로 오른쪽과 왼쪽 중 어디가 더 값이 적게 남았는지 체크를 해야한다. 

덱에서는 큐와 다르게 인덱스로 값을 알 수 있기때문에 덱을 사용해서 풀이하며 된다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> vec;
deque<int> dq;

int main() {
    int n, m;
    int cnt = 0;

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        dq.push_back(i);
    }

    for(int i = 0; i < m; i++) {
        int a;
        int left, right;
        
        cin >> a;
        
        for (int i = 0; i < dq.size(); i++) {
            if(dq[i] == a) {
                left = i;
                right = dq.size() - i;
                break;
            }
        }

        if (left <= right) {
            while(true) {
                if(dq.front() == a) {
                    dq.pop_front();
                    break;
                }
                dq.push_back(dq.front());
                dq.pop_front();
                cnt++;
            }
        } 
        else {
            while(true) {
                if(dq.front()== a) {
                    dq.pop_front();
                    break;
                }
                dq.push_front(dq.back());
                dq.pop_back();
                cnt++;
            }
        }
    }
    cout << cnt;
}

 

 

---

 

 

3. Feedback

- 큐는 인덱스로 접근 못하는것을 알고있어서 덱 또한 인덱스 접근이 안되는 줄 알았다. 마음이 급해 기능에 대해 대충알고 알고리즘을 풀었던 것에 대한 허점이 드러나는 것 같다. 깊이도 같이 채울 때가 된 것 같다.

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

728x90