글 읽기 - 시간초과 으악

minripex 4년 전 0

처음에는 행과열을 전부다 서로 비교하면서 없어지는 수를 구하는식으로했는데 이러면 시간복잡도떄문에 많이걸려서 시간초과가떳구나해서

2차원 배열을 첫번쨰열을 기준으로 순위를 정렬시켜서 오른쪽 열만으로 답을 구하려고했어요

왼쪽열이 12345 이렇게 순위로 되있으면 오른쪽열에서 이제 내림차순이안되는 숫자를 failnum로 칭해서 답을 구해봤는데

연산과정을 줄였다 생각했는데 그대로 시간초과가 납니다..

단지 이중for문때문에 이런걸까요 아니면 제가 아직도 불필요한 연산을 못줄여서 그런걸까요 ?

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)

int Compare(const void* first, const void* second) {
	if (*((int*)first) > * ((int*)second)) {
		return 1;
	}
	else if (*((int*)first) == *((int*)second))
		return 0;
	else
		return -1;
}

int main() {

	int gamecase;

	int arr[100000][2] = { };
	int cnt[20];      //최대 인원수 정답
	int i, j, k;

	int numgamer;
	int failnum = 0;

	scanf("%d", &gamecase);      //집단 수

	for (i = 0; i < gamecase; i++) {
		scanf("%d", &numgamer);

		for (j = 0; j < numgamer; j++) {
			scanf("%d %d", &arr[j][0], &arr[j][1]);
		}

		qsort(arr, numgamer, sizeof(int) * 2, Compare);       //첫번째 열 정렬


		for (j = 0; j < numgamer; j++) {                   //오른쪽 열 자기보다 큰수만나면 
														   //0으로바꾸고 지운수(failnum)1씩증가    
			for (k = j + 1; k < numgamer; k++) {
			chk:
				if (arr[j][1] == 0) {
					j++;
					goto chk;
				}
				if (arr[j][1] < arr[k][1]) {
					failnum++;
					arr[k][1] = 0;
				}
			}
		}

		/*for (k = 0; k < numgamer; k++) {                        // 시간초과
			for (l = 0; l < numgamer; l++) {
				if (k == l) {
					l++;
				}
				if (arr[k][0] > arr[l][0] && arr[k][1] > arr[l][1]) {
					failnum++;
					break;
				}
			}
		}*/

		cnt[i] = numgamer - failnum;
		failnum = 0;
	}




	for (i = 0; i < gamecase; i++) {              //케이스마다 최대인원수 출력
		printf("%d\n", cnt[i]);
	}
	return 0;

}

djm03178 4년 전 1

문제 풀이에서는 항상 1. 최악의 2. 시간 복잡도를 생각해야 합니다. 38, 40번째 줄의 2중 루프가 최악의 경우에 O(N^2)을 만들고 있기 때문에 통과할 수 없습니다.

minripex 4년 전 1

뭔가 알고리즘? 공부를 접한지 얼마안되서 시간복잡도를 처음 공부해보네요 이중for문말고 다른 방향으로 해결했습니다! 감사합니다

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

문제

문제

출처

ICPC

시간초과 으악

minripex 4년 전 0

djm03178 4년 전 1

minripex 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말