글 읽기 - 왜 시간초과가 나는지 궁금합니다.

akuby21 4년 전 0

문제를 보고 생각나는대로 코드를 작성하고 올바른 결과가 나오는 것은 확인하였습니다.

그런데 채점을 하니 시간초과가 떠서 어떤부분이 비효율적인지 알고 싶어서 질문드립니다.

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

typedef struct node *nodePointer;
typedef struct node {
	int data;
	nodePointer link;
}node;
nodePointer head = NULL;

void insert(int data) {
	nodePointer temp,tmp;
	temp = malloc(sizeof(*temp));
	temp->data = data; temp->link = NULL;

	if (head == NULL) {
		head = temp;
	}
	else {
		tmp = head;
		while (tmp->link != NULL) {
			tmp = tmp->link;
		}
		tmp->link = temp;
	}
}

void snailConnect(int nNum) {
	nodePointer temp,tmp;
	temp = tmp = head;
	for (; temp->link != NULL; temp = temp->link);
	for (int i = 0; i < nNum-1; tmp = tmp->link,i++);
	temp->link = tmp;
}

int nextSearch(int search) {
	nodePointer temp = head;
	for (int i = 0; i < search; i++, temp = temp->link);
	return temp->data;
}
int main() {
	int nNode, nQue, nNum;
	int data,search;
	scanf("%d %d %d", &nNode, &nQue, &nNum);
	for (int i = 0; i < nNode; i++) {
		scanf("%d", &data);
		insert(data);
	}
	snailConnect(nNum);
	for (int i = 0; i < nQue; i++) {
		scanf("%d", &search);
		printf("%d\n", nextSearch(search));
	}
}

snrnsidy 4년 전 1

코드에서 사용하신 search 변수의 크기는 최대 10억입니다. 코드를 보시면 search만큼 반복문을 도시는데 search가 10억인 데이터가 주어지면 당연히 시간초과가 날 수 밖에 없습니다.

akuby21 4년 전 0

너무 당연한걸 까먹고 있었네요 감사합니다!

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

문제

문제

출처

ICPC

왜 시간초과가 나는지 궁금합니다.

akuby21 4년 전 0

snrnsidy 4년 전 1

akuby21 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말