2-T 질문

Question

강의에 나온 이중 반복문으로 작성한 코드입니다. 그런데 제출했을 때 시간 초과가 나지 않는 이유가 뭔가요?? #include using namespace std; int n; int a[1000001]; int ret[1000001]; int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i < n; i++){ int j = i + 1; while(a[j] <= a[i]){ j++; if(j == n + 1) break; } if(j == n + 1)ret[i] = -1; else ret[i] = a[j]; } ret[n] = -1; for(int i = 1; i <= n; i++){ cout << ret[i] << " "; } return 0; }

kundol · Answer

안녕하세요, spiderman님 :) 질문하신 대로 이 코드는 최악의 경우 O(N²) 이 맞습니다. 그런데도 통과한 건 채점 데이터에 그 최악의 경우가 없어서입니다. 1. 이 코드의 최악의 경우 while(a[j] <= a[i])는 i 오른쪽에서 a[i]보다 큰 수가 나올 때까지 한 칸씩 이동합니다. 큰 수가 금방 나오면 몇 칸 만에 끝나지만, 끝까지 안 나오면 배열 끝까지 갑니다. - 내림차순 수열: 1000000 999999 ... 2 1 - 같은 값만 반복: 5 5 5 5 ... 5 (조건이 <=이라 같은 값도 계속 넘어갑니다) 이런 입력에서는 모든 i가 배열 끝까지 탐색합니다. 그러면 N(N-1)/2번을 돌게 되고, N = 1,000,000이면 약 5 × 10¹¹번이라 1초 안에 절대 끝나지 않습니다. 2. 그런데 통과한 이유 채점 데이터를 확인해 보니, 가장 큰 케이스(N = 약 27만)가 무작위로 섞인 수열이었습니다. 무작위 수열에서는 자기보다 큰 수가 보통 바로 근처에 있습니다. 그래서 이 케이스에서 안쪽 while이 원소 하나당 평균 15칸 정도만 돌았고, 전체로도 약 400만 번이라 시간 안에 끝난 것입니다. 정리하면 코드가 빠른 게 아니라, 데이터가 최악의 경우를 찌르지 못한 것입니다. + 해당 부분 보강하도록 하겠습니다. 감사합니다 .