Single Linked List, 링크드 리스트, 백준 1158

백준 1158


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

이 문제는 이번에 다뤄볼 링크드 리스트를 안쓰더라도 다양하게 풀 수 있습니다.

예를 들어 이처럼 그냥 배열을 통해 풀 수도 있습니다.

include <stdio.h>

int n, m, arr[5007];

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

	i = n - 1;
	int size = n;
	printf("<");
	while (size > 1) {
		i = (i + m) % size;
		printf("%d, ", arr[i]);
		--size;
		for (j = i; j < size; ++j) arr[j] = arr[j + 1];
		--i;
	}
	printf("%d>", arr[0]);

	return 0;
}

이 방식의 문제점은 한사람 한사람 죽을 때마다(ㄷㄷ…) 배열을 재구성 해야합니다.

예를 들어 총 7명이 있는데 3번 사람이 죽었으면, 4, 5, 6, 7 사람이 한칸씩 땡겨 앉아야 하죠.

이 문제에서는 최대 사람 수가 5000명이기 때문에 시간이 얼마 안걸리지만, 1억명이라면?

처음에 2번 사람이 죽는다면, 그 뒤에 있는 99999998명이 자리를 옮겨야 합니다.

시간이 엄청 많이 걸릴 것입니다.



Linked List


이러한 문제점을 해결할 수 있는 자료구조가 바로 링크드 리스트 입니다.

링크드 리스트에는 여러 종류가 있지만, 지금은 가장 기본이 되는 Single Linked List에 대해 살펴보겠습니다.

single_linked_list

일단 노드(Node)는 데이터와 주소값으로 이루어진 구조체입니다.

저 노드로 이루어진 자료구조가 싱글 링크드 리스트 입니다.

예를 들어 위에서는 teemo, jax, gnar의 데이터를 링크드 리스트로 저장한 형태입니다.

teemo 노드를 살펴보면 다음 노드인 jax로 갈 수 있고,

jax 노드를 살펴보면 다음 노드인 gnar 노드로 갈 수 있습니다.

gnar노드를 살펴보면 next가 NULL이므로 데이터의 끝이라는 걸 알 수 있습니다.


다음과 같이 노드를 추가한다면 어떻게 해야할까요?

linked_list_add1

이때는 원래 jax 노드를 가리키고 있던 teemo 노드의 next를 malphite를 가리키게 하면 됩니다.

그리고 malphite 노드의 next를 jax를 가리키게 하면 의도한대로 malphite를 teemo와 jax 중간에 추가할 수 있습니다.

linked_list_add2


그럼 노드를 삭제한다면?

linked_list_del1

jax 노드가 빠진다면 teemo 노드와 gnar을 연결 시켜야겠죠.

즉, teemo 노드의 next가 gnar 노드를 가리키게 하면 됩니다.

필요하다면 jax 노드와 gnar 노드의 연결까지 끊으면 됩니다.

linked_list_del2


이처럼 링크드 리스트는 배열과 비교해서 데이터의 삽입, 삭제가 빠릅니다.

배열을 하나 삽입하거나 삭제면, 삽입/삭제하는 위치 뒤쪽의 모든 데이터를 옮겨야 하는데,

링크드 리스트는 삽입/삭제되는 위치의 연결고리만 조금 수정해주면 되기 때문입니다.


하지만, 배열에 비해 데이터 탐색은 느립니다.

예를 들어 777번째 데이터에 접근하겠다라고하면, 배열은 그냥 arr[777]로 접근하면 됩니다.

하지만 링크드 리스트는 맨 처음 노드(위 예제에서는 teemo 노드)에 가서 776번 next를 통해 하나하나 이동해야합니다.



다시 문제로 돌아와서…


이 문제를 링크드 리스트로 접근해보겠습니다.

1번부터 N번 사람들을 각각 노드로 만듭니다.

그리고 i번 노드의 next는 i+1번 노드를 가리키게 합니다.

그리고 마지막 n번 노드는 1번 노드를 가리키게 하는 것이죠.


n번 노드부터 시작하여 m-1번 이동 후, 도착한 노드의 다음 노드를 삭제합니다.

노드 삭제하는 방법은 위에 설명되어 있습니다.


#include <stdio.h>

const int MAX = 5000;
int n, m;

struct Node {
	int d;
	Node* next;

	Node* myAlloc(int d, Node* n) {
		this->d = d;
		next = n;
		return this;
	}
}buf[MAX + 7], *cur;

int main() {
	scanf("%d %d", &n, &m);
	int i;

	for (i = n; i > 0; --i) cur = buf[i].myAlloc(i, cur);
	cur = &buf[n];
	cur->next = &buf[1];

	printf("<");
	while (cur->next != cur) {
		for (i = 1; i < m; ++i) cur = cur->next;
		printf("%d, ", cur->next->d);
		cur->next = cur->next->next;
	}
	printf("%d>", cur->d);

	return 0;
}