/<> 백준 1021번 : 회전하는 큐 (C언어)

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

 
 
배열의 양쪽 회전이 가능하기 때문에 덱을 이용해 풀었지만, 이후 제 코드를 보니 굳이 이중으로 하지 않고 단일 연결 리스트만으로 풀 수 있는 문제였습니다. 이중 연결 리스트를 만드는 이유가 왼쪽 이동과 오른쪽 이동 중 어느 방향이 더 짧은 지 알아내기 위함인데, 그냥 <배열에 남아 있는 원소 개수>와 <한 방향으로 특정 수의 위치까지 이동하는 데 필요한 이동 횟수>를 비교하면 쉽게 판단할 수 있습니다.
 
이동 횟수가 원소 개수의 절반을 넘으면 반대 방향으로 이동하는 게 더 빠르고, 절반을 넘지 못하면 해당 방향으로 이동하는 게 더 빠릅니다!!
 
그럼 반대 방향이 더 빠른 경우엔 그냥 <원소 개수 - 이동 횟수>가 반대 방향으로의 이동 횟수가 됩니다. 그래서 단일 연결 리스트만으로 풀 수 있습니다.
 
 
1. 원소들을 연결 리스트로 만듭니다. (코드는 덱으로 만들어져 있음)
 
2. 뽑아내려 하는 수들을 배열에 저장합니다.
 
3. 배열의 수가 연결 리스트의 헤더 부분이면 그냥 제거하고, 이외의 노드에 있으면 탐색을 통해 찾아내고 이동 횟수를 증가시키고 해당 노드를 제거합니다. 이 때 해당 노드를 헤더로 바꾸고 헤더 노드 삭제 함수를 사용합니다.
 
 
<코드>

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

typedef struct deck {
        int data;
        struct deck* llink;
        struct deck* rlink;
} deck;

typedef struct header {
        int size;
        struct deck* link;
} header;

int num[50];
int count = 0;

void delete(header*); // 뽑을 원소가 헤더에 있을 때
void shift(header*, int); // 뽑을 원소가 헤더에 없을 때

int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++) scanf("%d", &num[i]);

        header* head = (header*)malloc(sizeof(header));
        head->size = n;
        head->link = NULL;

        deck* curr = NULL;
        for(int i = 1; i <= n; i++) {
                deck* newnode = (deck*)malloc(sizeof(deck));
                newnode->data = i;
                newnode->llink = curr;

                if(curr == NULL) head->link = newnode;
                else curr->rlink = newnode;
                curr = newnode;
        }
        if(curr != NULL) {
                curr->rlink = head->link;
                head->link->llink = curr;
        }

        for(int i = 0; i < m; i++) {
                if(head->link->data == num[i]) delete(head);
                else shift(head, num[i]);
        }
        printf("%d\n", count);
        return 0;
}

void delete(header* head) {
        if(head->link == NULL) return;
        deck* denode = head->link;
        denode->llink->rlink = denode->rlink;
        denode->rlink->llink = denode->llink;
        head->link = head->link->rlink;

        head->size--;
        free(denode);
        return;
}

void shift(header* head, int n) {
        deck* curr = head->link;
        int idx = 0;
        while(curr->data != n) {
                idx++;
                curr = curr->rlink;
                if(curr->data == n) break;
        }

        head->link = curr;
        if(idx > head->size / 2) count += head->size - idx; // 왼쪽으로 회전
        else count += idx; // 오른쪽으로 회전

        delete(head);
        return;
}

 
 
단일 연결 리스트로 푼 거나 다름없기에, llink나 rlink를 쓰지 않아도 됐었습니다. (메모리 낭비 이슈)
 
이 문제를 풀면서 간단하지만 새로 배운 점이 있었습니다. 연결 리스트에 새로운 노드를 추가할 때 그동안 prev_node를 생성하여 연결 리스트의 마지막 노드까지 이동한 후에 <prev_node->link = new_node>의 방식으로 새로운 노드를 추가를 했습니다.
 
코드를 통해 보자면

for(int i = 0; i < size_of_list; i++) {
	node* new_node = (node*)malloc(sizeof(node));
	new_node->data = number;
	new_node->link = NULL;

	if(head->link == NULL) head = new_node;
	else {
		node* prev_node = head;
		while(prev_node->link != NULL) prev_node = prev_node->link;

		prev_node->link = new_node;
	}
}

 
연결 리스트를 만드는 과정을 생각해 보면 처음 for문 내부에서 while문을 사용하는 형태입니다. 시간 복잡도가 O(n^2)이죠.
 
하지만 반복문 바깥에 노드 하나를 만들고, new_node를 생성할 때마다 바깥 노드의 값을 new_node로 복사하면 반복문을 쓰지 않고 위의 prev_node 역할을 할 수 있습니다. (슬라이딩 윈도우 느낌)
 
다시 코드를 통해 보자면

node* prev_node = NULL;

for(int i = 0; i < size_of_list; i++) {
    node* new_node = (node*)malloc(sizeof(node));
    node->data = number;
    node->link = NULL;
    
    if(prev_node == NULL) head = new_node;
    else prev_node->link = new_node;
    
    prev_node = new_node;
}

 

시간 복잡도가 O(n)인 것을 확인할 수 있습니다. 엄청난 차이죠.
새로운 팁을 오늘 풀면서 배웠습니다.