✅ deque

문제

링크

풀이

1. 문제 접근

문제의 연산 종류를 따져보면

1. 맨 왼쪽 (첫 번째 원소)를 뽑는다.
2. 맨 왼쪽 (첫 번째 원소)를 맨 오른쪽 (마지막)에 넣는다.
3. 맨 오른쪽 (마지막 원소)를 맨 왼쪽 (첫 번째)에 넣는다.

주어진 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 문제이다.

즉, 원하는 원소를 뽑는 경우는 1번 연산에 의해 맨 왼쪽에서만 가능하고
큐를 이동하는 방법은 2, 3번 연산을 통해 수행한다.

2. 자료구조 선택과 그 이유

양쪽에서 pop과 push를 써야하는 양방향 순환 큐이므로 덱을 사용해야 한다.

3. 문제 해결 로직 (풀이법)

2, 3번 연산의 최솟값이라는 건 곧 큐의 이동을 최소화 하고 뽑는 것이 베스트라는 소리이다.
따라서 뽑고자 하는 원소가 큐의 왼쪽이나 오른쪽으로 최소한으로 움직여서 첫번째 위치에 위치해야 한다. (1번 연산으로 뽑아야하기 때문)

주의해야 할 점은 오른쪽으로 이동할 경우에는 본인도 맨 앞으로 이동해야 하기 때문에 이동 횟수에 + 1 을 해주어야 한다.

즉, 본인 기준 "왼쪽 원소의 수"와 "오른쪽 원소의 수 + 1" 을 비교하여 더 적은쪽으로 이동한다.

의사코드

cin >> num

// 왼쪽, 오른쪽 원소의 수 세기
for(i = 0 ~ dq.size){
	if(dq[i] == num){
    	left = i
        right = dq.size - left - 1
    }
}

// 왼쪽 이동
if(left <= right + 1){
	while(1){
    	if(dq.front == num) break;
        tmp = dq.front
        dq.push_back(tmp)
        dq.pop_front
        cnt++
    }
    dq.pop_front
}
else{ // 오른쪽 이동
    while(1){
    	if(dq.front == num) break;
        tmp = dq.back
        dq.push_front(tmp)
        dq.pop_back
        cnt++
    }
    dq.pop_front
}

cout << cnt

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

문제에서 양방향 큐라는 언급이 있어서 덱을 사용해야겠다는 판단 자체는 어렵지 않았지만 원소를 빼는 방향이 왼쪽 뿐이라 왼쪽으로 이동할 경우와 오른쪽으로 이동하는 경우 중, 최선의 방향을 찾는 과정에서 함정이 있었던 문제였다.