정렬의 시간복잡도는 O(NlogN)입니다. 현재 코드는 정렬을 K번 수행하므로, 총 O(KNlogN)이고, 대충 계산해 보면 1700억 정도 됩니다.
보통은 1억당 1초 정도가 수행된다고 보시면 되고, 최근엔 컴퓨터가 많이 빨라져서 정말 기초적이고 간단한 연산의 경우 최대 10억 회 정도까지가 1초 내의 연산량 상한입니다.
1700억회의 연산이 필요한 이 코드는 어떻게 하더라도 최악의 데이터를 통과할 수가 없습니다.
직접 매번 정렬하지 않고도 배열의 상태를 알아낼 수 있는 알고리즘을 생각해 보세요.
아직 초심자시라면, 조금 어려울 수도 있습니다.
jdouble2037 4년 전
제가 이렇게 https://www.acmicpc.net/problem/13415 이 문제를 풀려 진행하였는데, 예제와 다른 제 테스트 케이스를 입력했는데, 자꾸 시간 초과가 발생하네요 맨 처음에 cin과 cout 입/출력 함수를 사용하여 그런 줄 알았는데, scanf/prinft 함수로 바꾸어도 똑같은 시간초과가 계속 지속되네요. 대체 어느 부분이 이렇게 문제가 되는거죠 ㅠㅠ 모르겠어서 질문 올립니다. 감사합니다.