Baekjoon 17298 (오큰수)

Baekjoon 17298, 백준 17298 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <cstring>
#include <utility>
#include <stack>
#define MAX_N 1000000

int NGE[MAX_N+2];

int main() {

    // Initialization
    int N;
    scanf("%d", &N);
    std::pair<int, int> *pairArr = new std::pair<int, int>[N+2];      // save <i, Ai>
    for(int i = 1; i <= N; i++) {
        pairArr[i].first = i;
        scanf("%d", &pairArr[i].second);
    }

    // Initialize array NGE to -1
    memset(NGE, -1, sizeof(NGE));

    // Use a stack to solve problem
    std::stack<std::pair<int, int>> s;

    // Push pairs to the stack
    for(int i = 1; i <= N; i++) {
        // Pop every member in stack while pairArr[i].second is smaller than s.top()
        if(!s.empty()) {
            while(pairArr[i].second > s.top().second) {
                std::pair<int, int> topPair = s.top();
                s.pop();
                // Update topPair's NGE info
                NGE[topPair.first] = pairArr[i].second;
                if(s.empty()) break;
            }
        }
        s.push(pairArr[i]);
    }

    // Print answer
    for(int i = 1; i <= N; i++) {
        printf("%d ", NGE[i]);
    }

    delete[] pairArr;
}

이 문제의 경우에도 스택 단원에 있었기에 자연스럽게 힌트를 받고 들어가게 되었다. 아마 그렇지 않았다면 조금의 시간 투자가 더 필요했을 것이다.

채점 시에 70% 안팎에서 ‘틀렸습니다’ 가 떠서 특정 케이스에서 에러가 나는 것을 확인하였다. 다양한 경우를 디버깅 해보다가, 본인의 같은 코드와 같은 Input을 넣었을 때 10번 중 1번 꼴로 이상한 값이 섞여 나타나는 것을 확인하였다. 여기서 디버깅의 핵심이 됐던 점은 이상한 값의 범위 였다. 대략 32700 안팎의 랜덤 숫자가 포함되었는데, 여기서 $2^{15} = 32768$ 임을 떠올려 어디선가 overflow가 되지 않았을까..? 하는 생각을 해보게 되었다. 결국 배열을 너무 타이트하게 동적할당 해 주어 생긴 문제임을 알게 되었다.

보통 “아 이거 맞았다!” 했을 때 ‘틀렸습니다’를 맞이하면, 쉬운 부분에서 실수를 한 케이스다. 이 문제는 20분만에 찾았지만, 실제로 CP를 할 때라던지 코테를 볼 때는 치명적인 시간이 된다. 그런 면에서 한 가지 실수 요소를 배우게 되었으니 나름 유익한 삽질이였다고 생각한다.

본인은 풀이에서 기본적으로 pair를 하나의 요소로 두고 다루었다. pair가 담긴 stack이라던지 등등. 그러나 제출한 후에 다른 분들의 코드를 살펴보니 굳이 그럴 필요가 없음을 깨달았다. 내가 pair로 지정한 이유는 < int, int > = < $i$, $A_i$ > 와 같이 각 $A_i$ 의 값에 $i$ 의 정보를 계속 달고 다니게 하기 위해서였는데, 결국 로직 상 $A_i$ 가 순서대로 저장되기 때문에 $i$의 정보는 필요가 없었다. 본 코드는 짧은 편이었어서 pair로 복잡하게 짜도 시간이 오래 걸리거나 코드가 꼬이는 일은 없었지만, 앞으로는 전반적인 아이디어를 잡은 후, 구체화하는 과정에서 최대한 단순화 하는 것이 실수를 줄일 수 있는 방향이라고 생각하였다.