[자료구조] 백준 문제 풀이 - 1021 회전하는 큐

 

덱을 이용하는 문제
☞ 내가 문제 이해를 잘못 해서 시간이 오래 걸림

 

내 풀이

3가지 상황이 있다

1. 주어진 숫자가 바로 맨 앞에 위치해 있었던 경우

2. 왼쪽으로 이동해야 하는 경우

3. 오른쪽으로 이동해야 하는 경우

#include <iostream>
#include <deque>
using namespace std;

int main()
{
	deque <int> dq;
	int N; cin>>N;
	int M; cin>>M;
	int num;
	int result=0;
	
	for(int i=1; i<=N; i++) //덱에 숫자를 넣고 큐를 회전시킬 준비를 함
	{
		dq.push_back(i);
	}
	
	while(M--)
	{
		cin>>num;
		if(dq.front()==num)//
		{
			dq.pop_front();
			continue;
		}
		
		int left;
		int right;
		for(int i=0; i<dq.size(); i++)//left로 가야하는지 right로 가야하는지 판단
		{
		    if(dq[i]==num)
		    {
		        right=i;
		        left=dq.size()-i;
		        break;
		    }
		}
		if(right>left)//left로 가야하는 상황
		{
		    for(int i=0; i<left; i++)
		    {
		        dq.push_front(dq.back());
		        dq.pop_back();
		        result++;
		    }
		    dq.pop_front();
		}
		else//right로 가야하는 상황
		{
		    for(int i=0; i<right; i++)
		    {
		        dq.push_back(dq.front());
		        dq.pop_front();
		        result++;
		    }
		    dq.pop_front();
		}
	}
	cout<<result<<endl;
}

 

다른 사람의 풀이

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
    int count=0;
    deque<int> dq;
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i)
        dq.push_back(i);
    for (int i = 0; i < M; ++i) {
        int num;
        cin >> num;
        int index;
        for (int i = 0; i < dq.size(); ++i) {
            if (dq[i] == num) {
                index = i;
                break;
            }
        }
        if (index < dq.size() - index) {
            for (;;) {
                if (dq.front() == num) {
                    dq.pop_front();
                    break;
                }
                ++count;
                dq.push_back(dq.front());
                dq.pop_front();
            }
        }
        else {
            for (;;) {
                if (dq.front() == num) {
                    dq.pop_front();
                    break;
                }
                ++count;
                dq.push_front(dq.back());
                dq.pop_back();
            }
        }
    }
    cout<<count;
}

다른점: 다른사람들은 while문, 무한루프+if문 break를 사용하였다면 난 for문을 이용함