[210324][백준/BOJ] 1021번 회전하는 큐

문제

입출력

풀이

앞/뒤 둘다 push pop이 가능해야 하므로 STL deque를 이용해서 풀었다.
뽑아야 하는 원소가 front를 기준으로 왼쪽/오른쪽 어디가 가까운지만 파악하면 풀 수 있다.

코드

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

int main(void)
{
	int n, m, num, left, right, res = 0;
	cin >> n >> m;
	deque<int> DQ;

	for (int i = 1; i <= n; ++i)
		DQ.push_back(i);

	while(m--)
	{
		cin >> num;

		for (int i = 0; i < DQ.size(); ++i)
		{
			if (DQ[i] == num)
			{
				left = i;
				right = DQ.size() - i;
			}
		}

		while (true)
		{
			if (DQ.front() == num)
			{
				DQ.pop_front();
				break;
			}
			if (left <= right)
			{
				DQ.push_back(DQ.front());
				DQ.pop_front();
				res++;
			}
			else 
			{
				DQ.push_front(DQ.back());
				DQ.pop_back();
				res++;
			}
		}
	}
	cout << res;
}

느낀점

2시간정도 낑낑대고 문제를 푼거 같다.
deque를 통해 어찌어찌 문제를 풀다보니 입력 예제 4개는 다 정상적으로 출력됐지만 게시판에 올라온 반례들에 다 막혔다.

일단 왼쪽 오른쪽 중 최단거리를 찾아야한다는 것은 파악했지만 찾고자 하는 정수의 위치와 전체 길이에서 찾고자 하는 정수의 위치를 빼서 이를 비교하는거까지는 생각하지 못하였다.
그래서 아마 운좋게도 4개의 입력예제는 맞았지만 여러가지 반례들에 막힌게 아닌가 싶다.

바킹독님 강의를 들으면서 하나하나 알고리즘을 공부하고 문제를 풀다보니 어떠한 방법으로 풀면 풀릴거 같다는 생각은 들지만 이를 실제 코드로 구현하는게 아직까지는 어려운거 같다.

앞으로도 2시간 정도는 남의 코드를 보지말고 풀어보다가 못풀겠다는 생각이 들면 좋은 코드를 찾아서 어떠한 로직으로 푼 코드인지 파악하는 일을 해야 할거 같다.