백준, BOJ 1021번 회전하는 큐 C++ [CPP]

 

물론 생각은 한 번에 났으나 구현이 20분은 걸렸다.

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

---

 

처음 문제보면서.. ??

어떤 자료구조를 쓸까.. 만약 shift를 하면 앞 뒤 둘다에서 삭제 삽입이 일어나는구나.

-> Deque를 쓰자.

Double ended queue

 

왼쪽으로 미는 거랑 오른쪽으로 미는 거랑 구분을 해야겠다.

**덱을 복사해서 쓰고 이동횟수가 적은 쪽을 다시 원본으로 복사해서 쓰자.

-> 다른 방법이 바로 생각안나서 N도 적어서 그냥 복사하기로했음

 

** 중요한 것은 1번연산이다. 숫자를 세지 않기 때문에 우선 내가 손수 제거해주어야 한다.

이것을 빼먹고 연산을 하는 바람에 틀렸다.

 

** 내 코드에는 비어있는 줄이 많다. 일부러 그랬다. 짜기 편하고 보기 편하다.

 

---

 

#1 내 코드

**(21.11.25 코멘트 추가)

#include <iostream>
#include <deque>

int N, k;

using namespace std;
int main() {
    cin >> N >> k;
    
    deque<int> dq;
    deque<int> dq1;
    deque<int> dq2;

    for (int i = 1; i <= N; i++) {
        dq.push_back(i);
    }
    
    int sum = 0;

	
    //K번 연산
    while (k--) {
		
        //최소횟수로 움직인 덱을 각각 앞 뒤로 조사
        dq1 = dq;
        dq2 = dq;

        int val;
        int front = 0;
        int back = 0;

        cin >> val;

		//앞에서 부터 접근하면.. 몇번?
        while (dq1.front() != val) {
            dq1.push_back(dq1.front());
            dq1.pop_front();
            front++;
        }
        dq1.pop_front();
        
        
        //뒤에서부터 접근하면 .. 몇번?
        while (dq2.front() != val) {
            dq2.push_front(dq2.back());
            dq2.pop_back();
            back++;
        }
        dq2.pop_front();
	
		
        //둘 중 작은덱을 복사 count 더해줌
        if (front > back) {
            sum += (back);
            dq = dq2;
        }
        else {
            sum += (front);
            dq = dq1;
        }
		
    }
    //작은 횟수로 K번 움직인 후 카운터.
    cout << sum;
}

 

 

반성할 점

 

연산 이후에도 처리해주어야 할 것이 있는지

특히 여기선 1번연산을 세지 않기 때문에 간과하고 넘어갔다.

 

복사할 대상이 너무 크지는 않은지 -> 여기선 크지 않았다.