글 읽기 - C++ 왜 시간초과가 날까요?

whyknow0604 1년 전 0

Linked list 자료구조를 활용 하여 구현하려고 했습니다.

Insert 부분도 tail에 바로 붙혀주는 로직이니 O(1)

merge 부분도 두 배열의 size 만큼이니 O(n+m)이라고 생각하고 있습니다.

알고리즘 문제인가요 아니면 LinkedList가 문제인건가요?

#include <iostream>

using namespace std;

class Node1 {
public:
	Node1* next;
	int value;
	Node1(int value);
	Node1(Node1* next, int value);
};

Node1::Node1(int value)
{
	this->next = NULL;
	this->value = value;
}

Node1::Node1(Node1* next, int value)
{
	this->next = next;
	this->value = value;
}

class linkedList {
	public:
		int size;
		Node1* head;
		Node1* tail;
		linkedList(int size);
		linkedList(int size, Node1* head);
		void Insert(Node1* n);
		void print();
		linkedList* merge(linkedList* L1, linkedList* L2);

};

linkedList::linkedList(int size)
{
	this->size = size;
	this->head = NULL;
	this->tail = NULL;
}

linkedList::linkedList(int size, Node1* head)
{
	this->size = size;
	this->head = head;
	this->tail = head;
}

void linkedList::Insert(Node1* n)
{
	if (head == NULL) {
		head = n;
		tail = n;
	}
	else {
		tail->next = n;
		tail = tail->next;
	}
}

void linkedList::print()
{
	Node1* temp = head;
	while (temp != NULL) {
		cout << temp->value << " ";
		temp = temp->next;
	}
}

linkedList* linkedList::merge(linkedList* L1, linkedList* L2)
{
	linkedList* mergeList = new linkedList(L1->size + L2->size);
	
	Node1* L1Head = L1->head;
	Node1* L2Head = L2->head;
	mergeList->head = NULL;

	if (L1Head->value > L2Head->value) {
		mergeList->head = L2Head;
		mergeList->tail = L2Head;
		L2Head = L2Head->next;
	}
	else {
		mergeList->head = L1Head;
		mergeList->tail = L1Head;
		L1Head = L1Head->next;
	}
	
	int count = 0;
	while(L1Head != NULL && L2Head != NULL) {
		count += 1;
		if (L1Head->value > L2Head->value) {
			mergeList->Insert(L2Head);
			L2Head = L2Head->next;
		}
		else if (L2Head->value > L1Head->value) {
			mergeList->Insert(L1Head);
			L1Head = L1Head->next;
		}
		else if (L2Head == NULL && L2Head != NULL) {
			mergeList->Insert(L1Head);
			L1Head = L1Head->next;
		}
		else {
			mergeList->Insert(L2Head);
			L2Head = L2Head->next;
		}
	}
	if (L1Head == NULL && L2Head != NULL) {
		mergeList->Insert(L2Head);
	}
	else if (L2Head == NULL && L1Head != NULL) {
		mergeList->Insert(L1Head);
	}

	mergeList->print();

	return mergeList;
}

int main() {

	int LL1size = 0;
	int LL2size = 0;

	cin >> LL1size;
	cin >> LL2size;

	linkedList* LL1 = new linkedList(LL1size);
	linkedList* LL2 = new linkedList(LL2size);

	int value = 0;
	for (int i = 0; i < LL1size; i++) {
		cin >> value;
		Node1* n = new Node1(value);
		LL1->Insert(n);
	}

	for (int i = 0; i < LL2size; i++) {
		cin >> value;
		Node1* n = new Node1(value);
		LL2->Insert(n);
	}

	linkedList* ML = LL1->merge(LL1, LL2);
	return 0;
}

hych0502 1년 전 0

다음을 참고해주세요.

15552번: 빠른 A+B

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 왜 시간초과가 날까요?

whyknow0604 1년 전 0

hych0502 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말