c언어 1021번 회전하는 큐 (백준)

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

typedef struct Node{ //덱에서 사용할 노드
	int data;
	struct Node* before;
	struct Node* next;
}Node;

typedef struct Deq{ //덱
	Node* front;
	Node* rear;
	int cnt;
}Deq;

void init(Deq* d) { //초기화
	d->front = d->rear = NULL;
	d->cnt = 0;
}
int isEmpty(Deq* d) {return d->cnt == 0;} //비었는가?

void frontPush(Deq* d, int e) { //앞에 넣기
	Node* node = (Node*) malloc(sizeof(Node));
	node->next = node->before = NULL;
	node->data = e;
	
	if(isEmpty(d)) d->front = d->rear = node;
	else {
		node->next = d->front;
		d->front->before = node;
		d->front = node;
	}
	d->cnt++;
}

void backPush(Deq* d, int e) { //뒤에 넣기
	Node* node = (Node*) malloc(sizeof(Node));
	node->next = node->before = NULL;
	node->data = e;
	
	if(isEmpty(d)) d->front = d->rear = node;
	else {
		node->before = d->rear;
		d->rear->next = node;
		d->rear = node;
	}
	d->cnt++;
}

int frontPop(Deq* d) { //앞에서 꺼내기
	if(isEmpty(d)) return '0';
	Node* ptr = d->front;
	int tmp = ptr->data;
	d->front = ptr->next;
	free(ptr);
	d->cnt--;
	return tmp;
}

int backPop(Deq* d) { //뒤에서 꺼내기
	if(isEmpty(d)) return '0';
	Node* ptr = d->rear;
	int tmp = ptr->data;
	d->rear = ptr->before;
	free(ptr);
	d->cnt--;
	return tmp;
}

int top(Deq* d) {return d->front->data;}

int main(void) {
	Deq d;
	init(&d);
	
	int n, m, ans=0; //ans는 2. 3. 연산의 횟수를 저장합니다.
	scanf("%d %d", &n, &m);
	
	for(int i=1; i<=n; i++) backPush(&d, i); //1~n만큼 덱에 넣어줍니다.
	
	for(int i = 0; i<m; i++) {
		int tmp, cnt = 0;
		scanf("%d", &tmp);
		while(1) {
			//printf(">>%d\n", top(&d));
			if(tmp == top(&d)) { //만약 맨 앞이 꺼내고 싶은 것과 같다면
				ans += (cnt <= d.cnt/2) ? cnt : d.cnt-cnt; //2.의 횟수와, 3.의횟수 중 더 작은 것을 누적합니다.
				frontPop(&d);
				break;
			} 
			backPush(&d, frontPop(&d)); //2. 연산입니다.
			cnt++;
		}
	}
	printf("%d", ans);
}

 

풀이 : 덱

 

0. 덱을 구조체로 구현하거나, 배열로 구현합니다.

1. n, m을 입력을 받습니다.

2. 구현한 덱에, 1부터 N까지 1~N으로 넣어줍니다.

3. 연산2. 만을 하여 꺼내고 싶은 수를 찾은 다음, 연산 2을 한 것과 연산 3을 한 것 중 더 적은 것을 구해서 누적합니다.

4. 누적한 기회들을 출력합니다.

 

연산3 의 횟수 = 전체 덱의 요소 - 연산 2 의 횟수 입니다.

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐