코드의 수행시간이 어떻게 되나요? 가령이면, 매 질문이 모든 원소에 대해 가장 작은 수를 찾는다고 해 봅시다.

일단... 입/출력 부분을 제외하고 n=1000으로 하고, 수열을 1~1000까지(순서는 랜덤) 섞고, m=2로 해 보았습니다.

하나는 1~1000번째(즉, 수열 전체) 중 1번째 수,

또 하나는 100~500번째 중 200번째 수로 테스트 해 보았는데요,

결과가 거의 바로 나왔습니다.

(물론, Ubuntu에서 테스트 했습니다.)

하지만, n이 커지면 즉, 입력의 2번째 줄의 길이가 늘어나면,

일정 길이(C에서는 약 4KB, Java에서는 약 8KB)만큼만 읽히고 나머지는 잘리는 현상이 발생합니다.

따라서, 제가 테스트를 못한다는 것이죠.

여기에서는 n의 최댓값이 100000인데, 2000인 경우도 테스트를 못하고 있습니다.

어쩌면 좋을까요? ㅠ.ㅠ

시간복잡도의 개념에 대해 들어보신 적 있나요?

프로그램이 수행되는 연산 횟수를 대략적으로 나타내는 지표입니다.

현재 작성하신 코드는 M번의 쿼리에 대해, NlogN의 시간복잡도를 가지는 정렬을 매번 하고 있으니 총 MNlogN의 시간복잡도를 가집니다.

최대 입력인 N=10만, M=5000을 대입해 보면 85억 가량이고, 보통 프로그램의 수행 시간을 1초당 1억 번 가량으로 잡으니

너무 오래 걸립니다. 10배 빨라져도 시간제한을 거의 열 배 가까이 초과하는, 너무 느린 코드예요.

이 문제를 푼 사람들은 다른 시간복잡도를 가지는, 이론적인 계산량 자체가 훨씬 적은 솔루션을 작성하여 통과했다는 의미입니다.

이 문제는 기초적인 알고리즘이나 코드 레벨에서의 최적화로 해결할 수 있는 수준을 넘어, 좀 멀리 가야 하는 문제입니다.

심화 자료구조를 이용해야 풀 수 있는 문제이고, 현재 푸신 문제를 보았을 때, 아직 이 자료구조를 익히시기엔 조금 이른 시기가 아닌가 싶습니다.

안타깝지만 조금 더 강해져서 돌아와야 한다.. 라는 의미입니다 ㅠㅠ

나중에 고급 알고리즘과 자료구조를 배우신 뒤에 다시 한번 시도해 보세요!

아직 저에게는 무리였나봐요 ㅠ.ㅠ

그래도 포기하지 않고 인터넷 검색을 통해서, 결국은 풀었어요 ^^

댓글 주신 분들 감사합니다~!