[덱]-기본-회전하는 큐

 

< 덱 > - < 실버 4 >

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

1021번: 회전하는 큐

---

[ 1021 ] 회전하는 큐

 

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

:: 입력 ::

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

:: 출력 ::

첫째 줄에 문제의 정답을 출력한다.

---

 

원래 구현했던 코드랑은 인덱스를 구하는 방법이 다르고  작업이 끝난 후에 아 쓰다보니까 알겠다 내 원래 코드에서는 옮기기만 하고 실제로 삭제를 안 했음 그래서 숫자가 계속 늘어났던 거고 그래서 Q.pop_front(); 부분이 필요한거네 저게 해당되는 숫자를 빼주는 부분이네 ㅇㅋ

 

  정답  코드  

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    deque<int> Q;
    for (int i = 1; i <= n; i++) Q.push_back(i);

    int ans = 0;
    while (m--) {
        int t;
        cin >> t;
        int idx = find(Q.begin(), Q.end(), t) - Q.begin(); // t의 위치
        while (Q.front() != t) {
            if (idx <= Q.size() / 2) {
                Q.push_back(Q.front());
                Q.pop_front();
            }
            else {
                Q.push_front(Q.back());
                Q.pop_back();
            }
            ans++;
            // 여기서 ans를 통으로 증가시키는 거
            // 근데 이건 내가 원래 했듯이 if랑 else 안에 넣어도 같은 결과가 나올 거 같긴 함
        }
        Q.pop_front();
        // 여기서 이걸 왜 해주는지 ? 잘 모르겠네 
        // 이제 알겟슴
        // 이거는 Q.front() == t 일때 그 숫자를 빼주는 부분임
    }

    cout << ans;
}

 

1/16 - 정답코드 참고 find 함수를 사용하는 걸 자꾸 까먹음

 

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

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

   vector<int> nums;

   // 뽑아낼 숫자들을 순서대로 nums에 저장
   for (int i = 0; i < m; i++) {
      int k;
      cin >> k;
      nums.push_back(k);
   }

   deque<int> dq;

   // dq를 1-n까지의 숫자로 채움
   for (int i = 1; i <= n; i++) {
      dq.push_back(i);
   }

   for (int i = 0; i < nums.size(); i++) {
      // begin으로부터 몇 칸 떨어진 곳에 위치했는지 계산
      // find 함수의 존재 자체를 자꾸 까먹음
      int dis = find(dq.begin(), dq.end(), nums[i])-dq.begin();
      while (dq.front() != nums[i]) {
          // 앞으로 돌리는 게 더 빠른 경우
         if (dis < dq.size() - dis) {
            dq.push_back(dq.front());
            dq.pop_front(); cnt++;
         }
         // 뒤로 돌리는 게 더 빠른 경우
         else {
            dq.push_front(dq.back());
            dq.pop_back(); cnt++;
         }
      }
      dq.pop_front();
   }

   std::cout << cnt;
   
}