[코딩인터뷰 완전정복] 2.1 중복 없애기

Q : 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.

+ 임시 버퍼를 사용할 수 없다면 어떻게 풀 수 있을까?

 

 

우선 연결리스트를 준비한다.

#include <iostream>

struct node {
	int data;
	node *next;
};

class linked_list {
private :
	node *head, *tail;
public:
	linked_list() {
		head = NULL;
		tail = NULL;
	}

	void add_node(int n) {
		node *temp = new node;
		temp->data = n;
		temp->next = NULL;
		if (head == NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = tail->next;
		}
	}

	node* first() {
		return head;
	}
};

void printLinkedList(linked_list list) {
	if (list.first() == NULL) return;

	node* currentNode = list.first();
	while (currentNode->next != NULL) {
		printf("%d - ", currentNode->data);
		currentNode = currentNode->next;
	}
	printf("%d", currentNode->data);

	printf("\n");
}

 

#include <hash_set>

void RemoveDuplicate(linked_list list) {
	if (list.first() == NULL) return;

	std::hash_set<int> set;
	node* currentNode = list.first();
	node* previous;
	while (true) {
		if (*set.find(currentNode->data) == NULL) {
			set.insert(currentNode->data);
			previous = currentNode;
		}
		else {
			previous->next = currentNode->next;
		}
		if (currentNode->next == NULL) break;
		currentNode = currentNode->next;
	}
}

int main() {
	linked_list list;
	list.add_node(1);
	list.add_node(2);
	list.add_node(1);
	list.add_node(5);
	list.add_node(4);
	list.add_node(4);
	list.add_node(1);
	list.add_node(5);

	printLinkedList(list);
	RemoveDuplicate(list);
	printLinkedList(list);
}

원소를 hash set 에 담아 중복되는 원소가 있으면 그 노드를 지운다.

버퍼를 사용하는 대신 시간복잡도는 O(N)이다.

void RemoveDuplicate(linked_list list) {
	if (list.first() == NULL) return;

	node *currentNode = list.first();
	node *serchNode, *previousNode;

	while (true) {
		serchNode = currentNode->next;
		previousNode = currentNode;

		while (true) {
			if (serchNode->data == currentNode->data) {
				previousNode->next = serchNode->next;
			}
			else {
				previousNode = serchNode;
			}
			if (serchNode->next == NULL) break;
			serchNode = serchNode->next;
		}
		if (currentNode->next == NULL) break;
		currentNode = currentNode->next;
	}
}

int main() {
	linked_list list;
	list.add_node(1);
	list.add_node(2);
	list.add_node(1);
	list.add_node(5);
	list.add_node(4);
	list.add_node(4);
	list.add_node(1);
	list.add_node(5);

	printLinkedList(list);
	RemoveDuplicate(list);
	printLinkedList(list);
}

포인터 2개를 이용해 탐색하며 중복되는 원소가 있으면 지운다.

버퍼를 사용하지 않는다.

시간복잡도가 O(N²)이 되지만 공간복잡도는 O(1)이 된다.