jdouble2037   4년 전

#include <iostream>
#include <vector>
#include <algorithm></algorithm></vector></iostream>
using namespace std;
bool cmp_up(const int &a, const int &b){
 
 return a < b;
 
}
bool cmp_down(const int &a, const int &b){
 
 return a > b;
 
}
int main(void) {
 
 int n,k,a,b;
 
 scanf("%d" , &n);
 
 int e[100001];
 
 
 for(int i = 0; i < n; i++) {
 
 scanf("%d" , &e[i]);
 
 }
 
 scanf("%d" , &k);
 
 scanf("%d %d" , &a , &b);
 
 
 for(int p = 0; p < k; p++) {
 
 sort(e, e+a, cmp_up);
 sort(e, e+b, cmp_down);
 
}
 for(int z = 0; z < n; z++) printf("%-2d" , e[z]);
 
 
}

제가 이렇게 https://www.acmicpc.net/problem/13415 이 문제를 풀려 진행하였는데, 예제와 다른 제 테스트 케이스를 입력했는데, 자꾸 시간 초과가 발생하네요 맨 처음에 cin과 cout 입/출력 함수를 사용하여 그런 줄 알았는데, scanf/prinft 함수로 바꾸어도 똑같은 시간초과가 계속 지속되네요. 대체 어느 부분이 이렇게 문제가 되는거죠 ㅠㅠ 모르겠어서 질문 올립니다. 감사합니다.





portableangel   4년 전

정렬의 시간복잡도는 O(NlogN)입니다. 현재 코드는 정렬을 K번 수행하므로, 총 O(KNlogN)이고, 대충 계산해 보면 1700억 정도 됩니다.

보통은 1억당 1초 정도가 수행된다고 보시면 되고, 최근엔 컴퓨터가 많이 빨라져서 정말 기초적이고 간단한 연산의 경우 최대 10억 회 정도까지가 1초 내의 연산량 상한입니다.

1700억회의 연산이 필요한 이 코드는 어떻게 하더라도 최악의 데이터를 통과할 수가 없습니다.

직접 매번 정렬하지 않고도 배열의 상태를 알아낼 수 있는 알고리즘을 생각해 보세요.

아직 초심자시라면, 조금 어려울 수도 있습니다.

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