백준1021 (회전하는 큐)[C/C++]

🔗링크

1. 문제 풀이

이 문제는 Deque를 사용해 풀수 있다.
Deque는 양방향 큐로써 앞,뒤 방향으로 데이터를 push하거나 pop할수 있는 자료구조다
이를 사용하면 2번 동작을 사용할 때와 3번 동작을 사용할 때를 구현할 수 있다
또한 2번 동작 3번 동작 둘중 무엇을 쓰는게 최단동작횟수일 지 결정하는 방법은
꺼내자하는 원소의 위치가 Deque의 중간(Deque의size / 2)보다 앞이라면 왼쪽이동인 2번이 빠를것이고 뒤에 존재하면 오른쪽 이동인 3번을 택하면 된다.

ex)N = 9일때 2, 8을 꺼내보면
우선 원소는 1 ~ 9까지 있을것이고 중간은 N/2인 4번째 인덱스의 원소일 것이다.

우리가 꺼낼 원소는 1번째 인덱스의 2이기 때문에 첫 원소를 뒤로 보내는 동작2번을 하는것이 빠를것이다 그렇기에 동작2번을 1번 하고나면

꺼내고자 하는 원소를 최단동작으로 꺼낼수 있게 되고 다음 원소 8의 경우

Deque의 중간인 인덱스 4보다 뒤인 인덱스 5에 존재하기 때문에 오른쪽으로 이동하는 3번동작이 더욱 빠를것이기에 원소 8이 front로 오도록 3번동작을 반복하면 될것이다.

2. 코드

c++ Deque 사용 코드

#include<stdio.h>
#include<deque>
using namespace std;

int main() {
	int cnt = 0;
	int N ,M,x=0;
	deque<int> dq;

	scanf("%d %d", &N,&M);
	for (int i = 0; i < N; i++)dq.push_back(i + 1); //deq에 초기값 push
		
	while (M--) {
		int i = 0;
		scanf("%d", &x);
		for (i = 0; dq[i] != x; i++);
		if (i <= dq.size() / 2) {
			while (dq.front() != x) {
				dq.push_back(dq.front());
				dq.pop_front();
				cnt++;
			}
		}
		else {
			while (dq.front() != x) {
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
		}
		dq.pop_front();
	}
	printf("%d", cnt);

	return 0;
}

c 동적구현 코드

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
	int data;
	Node* r;
	Node* l;
};

typedef struct Deque {
	Node* front;
	Node* Back;
	int size;
};

void push_front(Deque* deq,int data) {
	  Node* newN = (Node*)malloc(sizeof(Node));
	  newN->data = data;
	  newN->l = NULL;
	  deq->front->l = newN;
	  newN->r = deq->front;
	  deq->front = newN;
	  deq->size++;
}

void push_back(Deque* deq, int data) {
	Node* newN = (Node*)malloc(sizeof(Node));
	newN->data = data;
	if (deq->size == 0) {
		newN->l = NULL;
		newN->r = NULL;
		deq->front = newN;
		deq->Back = deq->front;
	}
	else {
		newN->r = NULL;
		newN->l = deq->Back;
		deq->Back->r = newN;
		deq->Back = newN;
	}
	deq->size++;
}

int pop_front(Deque* deq) {
	Node* pop = deq->front;
	int data = pop->data;
	if (deq->front != deq->Back) {
		deq->front = deq->front->r;
		deq->front->l = NULL;
		deq->size--;
	}
	free(pop);
	return data;
}

int pop_back(Deque* deq) {
	Node* pop = deq->Back;
	int data = pop->data;

	deq->Back = deq->Back->l;
	deq->Back->r = NULL;
	deq->size--;
	free(pop);
	return data;
}

int findwhere(Deque* deq,int key) {
	Node* p = deq->front;
	int idx = 0;
	while (p->data != key) {
		idx++;
		p = p->r;
	}
	if (idx <= deq->size / 2)return 0;//idx의 위치가 deq의 중간보다 왼쪽일 경우
	else return 1;//idx의 위치가 deq의 중간보다 오른쪽일 경우
}

int main() {
	int cnt = 0;
	int N ,M,x=0;
	Deque* deq = (Deque*)malloc(sizeof(Deque));
	deq->front = NULL;
	deq->Back = NULL;
	deq->size = 0;

	scanf("%d %d", &N,&M);
	for (int i = 0; i < N; i++) //deq에 초기값 push
		push_back(deq, i + 1);

	while (M--) {
		scanf("%d", &x);
			if (findwhere(deq, x)) {
				while (deq->front->data != x) {
					push_front(deq, pop_back(deq));//찾는수가 중간보다 오른쪽일 경우 3번 수행
					cnt++;
				}
			}
			else {
				while (deq->front->data != x) {
					push_back(deq, pop_front(deq));//찾는수가 중간보다 왼쪽일 경우 2번 수행
					cnt++;
				}
			}
		pop_front(deq);	
	}
	printf("%d", cnt);

	return 0;
}

3. 후기

C++ std 함수를 쓰면 삶이 편해진다..(곧 c++로 갈아타야지..)