글 읽기 - 시간초과 나오는데 이유를 모르겠습니다 조언부탁드립니다!!

tprjs456 3년 전 0

시간초과나오는 이유를 알고싶습니다!

코드에 문제점이 있다면 조언부탁드립니다!!

#include<stdio.h>

int x[100001];
int y[100001];
int counting[200001];
int counting2[200001];


int main(void) {
	int N;
	int stop = 0;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &x[i]);
		scanf("%d", &y[i]);
	}

	for (int i = 0; i < N; i++) {
		counting[x[i] + 100000]++;
	}

	for (int i = 0; i < 200001; i++) {

		if (counting[i] != 0) {
			for (int j = 0; j < counting[i]; j++) {
				printf("%d ", i - 100000);
				stop = 0;
				for (int k = 0; k < N && stop == 0; k++) {

					if (x[k] == i - 100000) {
						counting2[y[k] + 100000]++;
					}
				}

				for (int a = 0; a < 200001 && stop == 0; a++) {
					if (counting2[a] != 0) {
						for (int b = 0; b < counting2[a] && stop == 0; b++) {
							printf("%d\n", a - 100000);
							counting2[a] = -1;
							stop = 1;
						}
					}
				}
			}
		}
	}
}

ioskya 3년 전 0

n이 10만이기때문에

시간복잡도가 nlogn인 정렬을 구현하거나 사용해서

정렬하셔야합니다. n^2 복잡도는 시간이 오래걸립니다.

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

문제

문제

출처

ICPC

시간초과 나오는데 이유를 모르겠습니다 조언부탁드립니다!!

tprjs456 3년 전 0

ioskya 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말