글 읽기 - 시간초과가 나는 이유가 뭘까요....

jeff5768 7년 전 0

왠만한 테스트 케이스는 다 돌아가는데 시간초과가 납니다..

어디서 무한루프라도 들어가는건가요?

적당한 케이스를 못찾겠네요ㅠㅠㅠ

도움 부탁드립니다!

#include <stdio.h>
int N, K;
int ar[500001];
int idxar[500001];
int tar[500001];
void findmin(int idx) {//버블소트해서 작은 값들의 인덱스들을 구해서 -1로 바꾸기
	int min = 10, i,t=0,j,temp;
	for (i = idx + 1; i < N; i++) {
		idxar[t] = ar[i];
		tar[t++] = i;
	}
	for (i = 0; i < t-1; i++) {
		for (j = 0; j < t - 1 - i; j++) {
			if (idxar[j] > idxar[j + 1]) {
				temp = idxar[j];
				idxar[j] = idxar[j + 1];
				idxar[j + 1] = temp;
				temp = tar[j];
				tar[j] = tar[j + 1];
				tar[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < K; i++) {
		ar[tar[i]] = -1;
	}
}
void process() {
	int idx = 0, max = 0, cnt = 0, i = 0,p=0;
	if (K == 0)return;
	while (1) {//앞뒤숫자 비교해서 앞에꺼가 작으면 없애기
		if (cnt > K||max==9) {
			if (idx == p) {
				findmin(idx);//뒤로 작은값을 찾아서 없애기
				return;
			}
			for (i = p; i < idx; i++) ar[i] = -1;
			K -= (idx-p);
			if (K == 0)return;
			else {
				i = idx+1, p = idx + 1, max = 0, cnt = 0, idx = 0;
			}
		}
		
		if (max < ar[i]) { 
			max = ar[i]; idx = i;
		}
		i++;
		cnt++;
	}
}
int main() {
	scanf("%d %d", &N, &K);
	int i;
	for (i = 0; i < N; i++) {
		scanf("%1d", &ar[i]);
	}
	process();
	for (i = 0; i < N; i++) {
		if (ar[i] >= 0)printf("%d", ar[i]);
	}
}

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

문제

문제

출처

ICPC

시간초과가 나는 이유가 뭘까요....

jeff5768 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말