글 읽기 - 18917번 c언어 연결리스트 시간초과

fnskh0606 2년 전 0

18917번 문제 연결리스트로 구현해봤는데요...

제가 줄일 수 있는 만큼 줄여봤는데 시간초과가 자꾸 뜨네요ㅠㅠ

혹시 저기서 시간많이 잡아먹는 코드가 있을까요...?

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

typedef struct node {
	int num;
	struct node* next;
}NODE;

NODE* insert(NODE* query, int data);
NODE* delete(NODE* query, int second);
void sumPrint(NODE* query);
void XOR(NODE* query);

int main() {
	NODE* query = (NODE*)malloc(sizeof(NODE));
	query->next = NULL;
	query->num = 0;
	int n;
	int first, second;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &first);
		if (first < 3) {
			scanf("%d", &second);
		}
		switch (first) {
		case 1:
			query = insert(query, second);
			
			break;

		case 2:
			query = delete(query, second);
			
			break;

		case 3:
			sumPrint(query);
			
			break;

		case 4:

			XOR(query);
			

			break;

		default:
			break;
		}
	}

}

NODE* insert(NODE* query, int data) {
	NODE* list = (NODE*)malloc(sizeof(NODE));
	
	list->num = data;
	list->next = query;
	
	return list;

}

NODE* delete(NODE* query, int second) {
	NODE* list = query;
	NODE* pre = NULL; 
	pre = list;
	list = list->next;
	while (list != NULL){
		if (list->num == second) {
			pre->next = list->next;
			return query;
		}

		else{
			pre = list;
			list = list->next;
		}
	}

	return query;
}

void sumPrint(NODE* query) {
	int sum = 0;
	NODE* list = query;
	while (list != NULL) {
		sum += list->num;
		list=list->next;
	}
	printf("%d\n", sum);
}

void XOR(NODE* query) {
	int sum = 0;
	NODE* list = query;
	while (list != NULL) {
		sum ^= list->num;
		list = list->next;
	}
	printf("%d\n", sum);
}

kdr06006 2년 전 1

M이 최대 500,000 입니다.

명령어가 add와 sum이 번갈아 나온다고 해봅시다.

그리고 sum의 시간 복잡도는 O(배열의 길이) 입니다.

그럼 1 + 2 + 3 + 4 + ... + 250,000 이고 이는 250,000 * 250,001 / 2 라서 제한시간 2초 내에 못돌아갑니다.

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

문제

문제

출처

ICPC

18917번 c언어 연결리스트 시간초과

fnskh0606 2년 전 0

kdr06006 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말