BOJ17298 오큰수

아이디어

---

주어진 n개의 값들이 들어있는 배열을 거꾸로 탐색하고 2중 for문으로 다시 정방향 탐색하며 비교하는 방식을 사용했다. 미리 찾아둔 오큰수 인덱스와 비교해가며 찾기 때문에 깡으로 정방향 탐색하는 것보다는 시간이 덜 걸릴것 같다는 생각이였다.

memset(nge, -1, sizeof(int) * 1000000);

for (int i = 0; i < n; i++)
    cin >> arr[i];

for (int i = n - 2; i >= 0; i--) {
    for (int j = i; j < n - 1; j++) {
        if (arr[i] < arr[j + 1]) {
            nge[i] = j + 1;
            break;
        }
        else if (nge[j] >= 0) {
            if (arr[i] < arr[nge[j]]) {
                nge[i] = nge[j];
                break;
            }
            else
                j = nge[j] - 1;
        }
    }
}

하지만 시간초과가 났고, 더 이상 아이디어가 떠오르지 않아 문제 분류를 확인했더니 스택이 있었다.

해답

---

배열은 정방향으로 탐색한다. 스택을 선언하는데, 여기에는 배열 요소들의 인덱스를 넣는다.

배열을 탐색하며 스택에서 값을 꺼내 보고 현재 탐색중인 숫자보다 작다면 아무것도 하지 않는다. 만약 꺼내본 숫자가 현재 탐색중인 숫자보다 크다면 해당 값을 pop하고 해당 인덱스의 nge배열에 현재 탐색중인 값을 저장한다.

while문을 돌면서 스택이 다 비거나 더 큰수가 나오기 전까지 반복한다. 반복문이 끝나면 스택에 현재 탐색중인 숫자의 인덱스를 저장한다.

이런식으로 진행하면 for문 한번만 도는 것으로 오큰수를 모두 구할 수 있다.

memset(nge, -1, sizeof(int) * 1000000);

for (int i = 0; i < n; i++)
    cin >> arr[i];

stack<int> s;
for (int i = 0; i < n; i++) {
    while (!s.empty()) {
        if (arr[i] > arr[s.top()]) {
            nge[s.top()] = arr[i];
            s.pop();
        }
        else
            break;
    }
    s.push(i);
}