궤도

문제 풀이 이중 for문을 쓰면 아주 쉬운데...시간제한때문에 시간복잡도를 줄여야한다. 이 문제를 푸는 아이디어는 오큰수를 구하지 못한 수를 스택에 저장하는 것이다. 더 자세하게 말하자면 오큰수를 구하지 못한 수의 인덱스를 스택에 저장하면 되겠다. 오큰수를 구하지 못한 수(A)를 스택에 저장하고, 그 뒤로 입력되는 수(B)에 대해 B가 A의 오큰수가 될 수 있는지 확인한다. 될 수 있다면 배열의 A 인덱스 값을 B로 바꿔준다. 마지막까지 스택에 남아있는 수는 오큰수를 구하지 못한 것이므로 -1로 바꿔준다. 소스코드 #include #include using namespace std; int num_arr[1000000]; void oaken(int length) { stack index; //오큰수를 구..