[백준][C] 1021번 회전하는 큐

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

 

문제를 처음에 보고 무슨 소리인가 이해하는데 시간이 좀 걸렸다.

 

입출력은 생각보다 간단했다.

 

입력으로 들어온 N이 10이라면

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 이 들어간 큐에서

 

M으로 입력받은 숫자를 1번 연산으로 빼내면 되는 문제다.

 

만약 N이 10, M이 3이고 2, 9, 5가 입력받았다면

2, 3번 연산을 통해 1 ~ 10이 들어간 큐에서 2, 9, 5를 1번 연산으로 빼내도록 하는 문제이다.

 

이 과정에서 사용된 2, 3번 연산의 개수를 출력하면 된다.

 

N도 최대가 50이고 시간도 2초라 시간이 매우 넉넉한 문제다.

 

일단 손으로 풀어보며 과정을 살펴보자

위에서 말한 예제를 살펴보자

여기서 2, 9, 5를 빼내야한다.

 

1. 우선 2번 연산으로 왼쪽으로 한칸 보낸다. (1번)

2. 1번 연산으로 숫자 2를 빼낸다.

3. 숫자 9를 오른쪽으로 3번 보내는게 9를 1번 위치로 보내는 제일 빠른 방법이다. (3번)

4. 1번 연산으로 숫자 9를 빼낸다.

5. 숫자 5의 경우 오른쪽도 4번, 왼쪽도 4번 움직여야 1번 위치로 이동할 수 있기 때문에 어디로 가든 상관 없다.  (4번)

 

따라서 총 합은 1 + 3 + 4 = 8로 8번의 이동으로 원하는 숫자를 빼낼 수 있다.

 

여기서 알 수 있는 사실은 

큐의 중심을 기준으로

왼쪽에 있는 숫자들은 2번 연산만 사용하는게 최단 거리이고,

오른쪽에 있는 숫자들은 3번 연산만 사용하는 게 최단 거리이다.

 

이제 이 방법을 사용해 계산하면 된다.

 

여기서 사용할 큐는 직접 이중 연결리스트를 사용해 구현하였다.

 

코드 보기

#include <stdio.h> 
#include <stdlib.h>
#pragma warning(disable:4996)

typedef struct node {
	int data;
	struct node* next;
	struct node* prev;
} Node;

Node* head = NULL;
Node* tail = NULL;
int cnt = 0;

void push(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;

	if (head == NULL) {
		head = newNode;
		tail = newNode;
	}
	else {
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
	cnt++;
}

int pop() {
	if (head == NULL)
	{
		printf("empty\n");
		return -1;
	}


	int d = head->data;
	Node* temp = head;
	head = head->next;

	if (head == NULL)
	{
		tail = NULL;
	}
	else
	{
		head->prev = NULL;
	}

	free(temp);
	cnt--;
	return d;
}

void moveLeft()
{
	int d = pop();
	push(d);
}

void moveRight()
{
	Node* temp = tail;
	tail = tail->prev;
	tail->next = NULL;

	temp->prev = NULL;
	temp->next = head;
	head->prev = temp;
	head = temp;
}

int findIdx(int d)
{
	Node* p = head;	
	int i = 0;
	while (p != NULL)
	{
		if (p->data == d)
			return i;
		p = p->next;
		i++;
	}
}


int findNum(int d)
{
	int sum = 0;
	if (head->data == d)
	{
		pop();
		return 0;
	}

	int idx = findIdx(d);
	if (idx > cnt / 2)
	{
		while (head->data != d)
		{
			moveRight();
			sum++;
		}

		pop();
		return sum;
	}
	else
	{
		while (head->data != d)
		{
			moveLeft();
			sum++;
		}

		pop();
		return sum;
	}
}

int main()
{
	int N, M;
	int d, ans = 0;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
	{
		push(i);
	}

	for (int i = 0; i < M; i++)
	{
		scanf("%d", &d);
		ans += findNum(d);
	}

	printf("%d\n", ans);

	return 0;
}