글 읽기 - C언어 시간초과 질문드립니다.

home2895 3년 전 0

시간복잡도를 일단 생각 안하고 출력이라도 잘 나오게 먼저 소스를 짰습니다.

예제들 입력하면 출력은 잘 나오는데 제출 해보면 4%에서 시간초과 에러가 발생합니다.

시간복잡도를 더 낮춰야겠죠???

혹시 어떻게 하면 될지 조언 좀 부탁드려요ㅜㅜ

#pragma warning(disable:4996)

#include <stdio.h>

int arr[100000] = { 0, };
int ar[100000] = { 0, };


int main(void)
{
	int N;
	int tmp1;
	scanf_s("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf_s("%d %d", &arr[i], &ar[i]);
	}
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (arr[i] > arr[j]) {
				tmp1 = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp1; // x 오름차순
				tmp1 = ar[i]; // y 같이 바꾸기
				ar[i] = ar[j];
				ar[j] = tmp1;
			}
		}
	}
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (arr[i] == arr[j]) { // x같으면
			if (ar[i] > ar[j]) { // y 오름차순
				tmp1 = ar[i];
				ar[i] = ar[j];
				ar[j] = tmp1;
			}
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		printf("%d %d\n", arr[i], ar[i]);
	}

	return 0;
}

djs100201 3년 전 0

mergesort,quicksort등을 공부해보시기 바랍니다.

특히 quicksort는 c언어에 내장함수가 있습니다.

home2895 3년 전 0

빠른답변 감사드립니다!!

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

문제

문제

출처

ICPC

C언어 시간초과 질문드립니다.

home2895 3년 전 0

djs100201 3년 전 0

home2895 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말