BOJ - 1021 회전하는 큐 해결 전략 (C++)

• 문제 링크
  백준 1021번 - 회전하는 큐

해결 전략

  본 포스팅은 반성문(?)과 같은 포스팅이다. 문제 자체는 맞추긴 했는데, deque stl 대신 list stl을 사용해서 괜시리 더 복잡한 프로그래밍을 자초했다는 것을 잊지말자는 취지이다.

  list stl은 인덱싱이 안된다. 그래서 iterator을 사용해야하는데, 이건 본인이 몰랐던 사실인데, 같은 양방향 리스트 역할을 하는 deque의 경우엔 stl에서 at이라는 내장 함수를 통해 인덱스과 유사한 기능을 제공한다는 점이다.

deque stl은 at 내장 함수를 이용해 인덱싱이 가능하다.

  이 사실이 왜 중요하냐면, 본 문제의 해결 알고리즘이, "찾고자 하는 값이 선형 구조 위의 위치해있는 곳을 기준으로 좌측의 길이와 우측의 길이를 비교해 더 짧은 쪽을 택하는 것"이 핵심이기 때문이다.

  만약 이를 iterator로 하면 괜히 선형 Traverse가 필요한데, deque stl을 이용했다면 이를 단순한 뺄셈으로 처리할 수 있었기 때문이다(물론, 찾고자 하는 요소의 인덱스를 찾는 과정은 똑같지만, 이 방식이 선형 순회를 한 번 더 줄여줄 수 있고, 무엇보다 가독성이 높아지기 때문에 이 방법이 더 좋은 것임.)

  물론, 본인이 택한 방식이 안 좋은 방식은 아닐 수 있다. 알고리즘의 구성은 오히려 더 잘 보여주기 때문이다. 하지만, 본 문제는 쉬운 문제이기 때문에 가독성이 더 중요할 것이다. 무튼, 각설하고 앞으로는 다음을 잘 지키도록 하자.

양방향 입출력이 가능한 선형 자료구조가 필요한 순간이면 list도 좋지만, deque도 고려하자.

  아래는 코드이다.

#include <iostream>
#include <list>
#include <deque>
// BOJ - 1021 Rotating Queue
using namespace std;

list<int> rq;
int pick[51];

void leftTraverse(int leftLen, int *sum) {
	(*sum) += leftLen;
	for (int i = 0; i < leftLen; i++) { rq.push_back(rq.front()); rq.pop_front(); }
}

void rightTraverse(int rightLen, int *sum) { 
	(*sum) += (rightLen + 1);
	for (int i = 0; i <= rightLen; i++) { rq.push_front(rq.back()); rq.pop_back(); }
}

int solve(int n, int m) {
	int pickCnt = 0, leftLen, rightLen, sum = 0;
	bool equalLeft, equalRight;

	while (pickCnt != m) {
		leftLen = rightLen = 0; equalLeft = equalRight = false;

		if (rq.front() == pick[pickCnt]) {
			rq.pop_front();
			pickCnt++;
			continue;
		}

		for (list<int>::iterator iter = rq.begin(); iter != rq.end(); iter++) {
			if ((*iter) == pick[pickCnt]) break;
			if ((*iter) == pick[pickCnt + 1]) equalLeft = true;
			leftLen++;
		}
		for (list<int>::reverse_iterator riter = rq.rbegin(); riter != rq.rend(); riter++) {
			if ((*riter) == pick[pickCnt]) break;
			if ((*riter) == pick[pickCnt + 1]) equalRight = true;
			rightLen++;
		}

		if (leftLen < (rightLen + 1)) leftTraverse(leftLen, &sum);
		else if (leftLen > (rightLen + 1)) rightTraverse(rightLen, &sum);
		else {
			if (equalRight) rightTraverse(rightLen, &sum);
			else leftTraverse(leftLen, &sum);
		}
	}

	return sum;
}

int main(void) {
	int n, m;

	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> pick[i];
	for (int i = 1; i <= n; i++) rq.push_back(i);
	cout << solve(n, m);

	return 0;
}