바킹독 0x07 문제2 / 백준 1021번 회전하는 큐

 

덱.... 을 배우자마자

다음 문제가 회전하는 큐.. 라니

이름만 들었을 땐..ㅇㅅㅇ 싶지만..

고민해 보도록 하자! 

 

오늘 내 꿈에

꽃을 순간적으로 무럭무럭 키우고 풍성하게 하는 능력을 가진

잠자리? 체 를 가지고 꽃을 키우러 가는?! 꿈을 꿨다.

되게 고고학 같은데 몽환적이었다.

나만 할 수 있는 일이라 즐거웠는데... 나중엔 너도나도 할라 해서 아쉬웠다.

지하로 들어가 야하기 때문에 두려움도 있었는데..

생각해 보니 몰래 갔어야 했는데 다른 사람들한테 들켜서 깼다....

떼잉..

 

다음의 나, 꽃을 키우러 갈 수 있을까...?

---

 

아니.. 정답비율이.. 60 퍼가 넘는데..

문제 이해조차 못했다..................

다들 똑똑하구나..

 

그 뜻은... 쉽다는 건가?! 아따 모르겠다.

 

20분째 됐을 때..

지피티에게 물어봤다.

지피티는 쉽게 설명해 준다며 알려주었다.

 

 

오... 오케이 이해.. 했어

 

 

 

오............ 이런 패턴이 있구나.. 신기하네오

2번 연산의 경우 인덱스만큼 해주면 되고

3번 연산의 경우 크기 - 인덱스만큼 해주면 되군!

 

오케이.. 반쯤 이해했으니 한번 풀어보겠습니다.

 

한 시간 정도? 풀었는데 포기했습니다.

 

#include <bits/stdc++.h>
using namespace std;

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

    int a, b;
    cin >> a >> b;
    deque<int> DQ;

    for (int i = 1; i <= a; i++)
    {
        DQ.push_back(i);
    }

    int ans = 0;
    for (int i = 1; i <= b; i++)
    {
        int n;
        cin >> n;
        int idx = find(DQ.begin(), DQ.end(), n) - DQ.begin();
        while (DQ.front() != n)
        {
            if (idx < (int)DQ.size() - idx)
            {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            }
            else
            {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            ans++;
        }
        DQ.pop_front();
    }
    cout << ans;
}

 

헷갈렸던 부분들을 정리하자면..

 

1. 덱에 값 넣기

 

1부터 10까지 넣어야 할 때 사실 이전에는

...ㅋㅋ

 for (int i = 1; i <= a; i++)
    {
        DQ [i - 1] = i;
    }

 

이렇게 했었다. 생긴 건.. 분명 될 거 같은데? 안된단다.

 

먼저 덱의 방식은

원소를 하나씩 추가 ( push ) 해줘야 하는 친구!

즉

push_front나 back 둘 다

애초에 원리가 크기가 한 칸 늘어나며 거기에 값이 들어가기 때문에

크기 관리가 자동? 인 셈

 

하지만 내 식처럼 하면..

배열처럼 생각했기 때문에..

 

사이즈를 모르면 인덱스로 접근할 수 없다고 한다.

 

그래서 사이즈를 정해놓는 방식도 있다고 한다.

DQ.resize(a) 이렇게 a만큼 확보하면? 된다고 한다.

근데 이건 너무 비효율적 아닌가!!!! 가변적인 게 매력인 친구인데..

 

 

 

2. idx 정해주기

위에 지피티가 이야기해 줬듯

idx를 알아야 한다.

그래야 왼쪽으로 당길 땐 인덱스만큼,

오른쪽으로 땡길땐 크기 - 인덱스 이기 때문!

 

그 인덱스를 구하는 방법은 find 함수를 사용한다.

이 std::find라는 친구는

주어진 범위에서 특정 값과 일치하는 요소를 처음부터 끝까지 찾아서 그 위치를 반환하는 함수

 

위치반환이기 때문에

사실 저 find만 계산하면 n이 들어간 주소값이 들어가 있다.

그렇기 때문에 첫 번째 주소를 빼줘야 한다.

 

약간 뭐 쉽게 설명하면

1008번 주소지의 값에다가 1000을 빼줘서

idx를 8로 받아오게 되는 것이다. 

 

3. while문으로 맨 앞에 값이 올 때까지 왼쪽 오른쪽 돌립니다.

 

자, 우리는 최솟값을 구해야 하기 때문에

idx가 왼쪽에 있는 값 오른쪽으로 밀기 23451

size - idx 가 오른쪽값 왼쪽으로 밀기 51234

 

회전을 한 횟수 더해주기 ans++;

그리고 빼주기

 

 

 

생각보다 어려운데?! 내일 다시 와서 풀어본다!!!!

내일 푼다 진짜!!

또 풀어!!!