백준 1021번 : 회전하는 큐

김채원·2025년 4월 3일

백준

문제 분석

큐의 크기 N
뽑아내려고 하는 수의 개수 M
뽑아내려고 하는 큐에서의 원소 위치가 순서대로 주어진다.
큐에서 원소를 다 뽑기 위해 실행한 2번, 3번 연산의 최소 횟수를 출력한다.

연산 종류

원소 뽑기 : 맨 앞에서만 원소 제거 가능 = pop_front()
왼쪽으로 한 칸 이동 : 맨 앞의 원소가 맨 뒤로 이동 = pop_front() , push_back(front())
오른쪽으로 한 칸 이동 : 맨 뒤의 원소가 맨 앞으로 이동 = pop_back() , push_front(back())

구현 절차

원소가 뽑혀지기 위해 맨 앞까지 가기 위한 이동 횟수가 최소여야 한다.

덱의 크기만큼 원소를 넣는다. (1부터 n까지)
뽑을 원소의 덱 안에서의 위치(인덱스)를 구한다.
뽑을 원소가 맨 앞으로 올 때까지 이동 후 연산 실행 총 횟수를 저장한다.
3-1. 뽑을 원소가 왼쪽(앞)과 가까울 경우 : 2번 연산을 실행한다.
3-2. 뽑을 원소가 오른쪽(뒤)와 가까울 경우 : 3번 연산을 실행한다.
뽑을 원소를 덱에서 pop() 한다.

내 풀이

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

int n, m, digit; 
deque<int> deq;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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

	int cnt = 0; // 연산 횟수
	for (int i = 0; i < m; i++) {
		
		// 뽑을 원소를 입력한 순서대로 처리
		cin >> digit;

		// deq.begin()는 인덱스 0인 원소를 가리킨다
		int idx = find(deq.begin(), deq.end(), digit) - deq.begin(); // 덱에서의 해당 원소 위치

		// 뽑을 원소가 맨 앞에 올 때까지
		while (deq.front() != digit) {
			
			if (idx < deq.size() - idx) {
				deq.push_back(deq.front()); // 2번 연산 : 왼쪽으로 한 칸 이동
				deq.pop_front(); // 왼쪽에 더 가깝게 위치해 있을 때
			}
			else { 
				deq.push_front(deq.back()); // 3번 연산 : 오른쪽으로 한 칸 이동
				deq.pop_back(); // 오른쪽에 더 가깝게 위치해 있을 때
			}

			cnt++; 
		}
		
		deq.pop_front(); // 맨 앞의 원소 뽑기
		
	}

	cout << cnt;

}

✅ find(start_iterator, end_iterator, value)

<algorithm> 헤더에 정의

지정된 범위 내에서 특정 값을 찾아 첫 번째로 일치하는 위치를 반환하는 함수

순차적으로 탐색 = 선형 탐색 = 데이터를 맨 앞부터 하나씩 검사하는 방식

시간복잡도 : $O(n)$

매개변수

start_iterator : 탐색을 시작할 반복자, 탐색 범위의 시작 위치
end_iterator : 탐색을 끝낼 반복자, 탐색 범위에 포함X
value : 찾고자 하는 값

반환 값

탐색 성공 : 찾은 원소의 반복자
탐색 실패 : 마지막 원소의 그 다음 위치 주소값 (의미 없는 값)

✅ deq.size() - idx

뽑으려는 원소가 맨 뒤(끝)로 이동하기 위해 오른쪽으로 이동해야 하는 횟수

✅ size()에 대해 주의할 점

여기서는 idx가 항상 deq.size()보다 작아서 문제가 없지만 .size() 는 unsigned int 이기 때문에 만약 idx가 deq.size()보다 컸다면 overflow가 발생하여 의도한대로 동작하지 않을 수 있다. 따라서 size()로 받아온 값에 대해서는 항상 안전하게 (int)deq.size() 이런 식으로 형변환 해주는 것이 좋다.

바킹독 풀이

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

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  deque<int> DQ;
  for (int i = 1; i <= n; i++) DQ.push_back(i);
  int ans = 0;
  while (m--) {
    int t;
    cin >> t;
    int idx = find(DQ.begin(), DQ.end(), t) - DQ.begin(); // idx : t가 있는 위치
    while (DQ.front() != t) {
      if (idx < 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;
}