글 읽기 - 기존 풀이와 약간 다른 접근법? 조건이 올바른지 확인해주세요....

chackcooking 2년 전 1

안녕하세요.

올바른 스택 수열 인지 확인 - bool IsAlright

top : 지금까지 확인한 원소 중 가장 큰 수
N : 배열의 범위, 배열에서 가장 큰 원소

Stack의 구조 상, 밑(상대적으로 작은 수) - 위(상대적으로 큰 수)로 들어가게 됩니다.

그리고 꺼냈을 때, 위를 먼저 꺼내게 되므로 (상대적으로 큰 수)가 무조건 먼저 나오게 됩니다.

따라서 이 원소들 중 가장 큰 수 N (절대적 큰 수)가 수열에서 나온 이후로는, 무조건 내림차순의 형태로 수열이 만들어 질 것이라 생각합니다.

즉, 올바른 스택 수열인지 확인하는 방법은 '가장 큰 수의 등장 전/후'로 나누었습니다.

등장 전 - 지금까지 확인한 원소 중 가장 큰 수(이하 top)을 이용하여 확인
등장 후 - 이후 수열이 내림차순을 따르는지 확인

*등장 전 확인 방법 - 다음 수가 top보다 작은 경우는 Stack에서 값을 꺼내는 경우 밖에 없다. 따라서 top보다 높은 숫자가 나올때 까지는, 이또한 내림차순을 따를 것.

위 조건(등장 전/후)을 따른 경우, 이 수열은 올바른 스택일 것이다!

올바른 경우, 일정한 규칙으로 +(push), -(pop) 출력

top : 지금까지 확인한 원소 중 가장 큰 수
N : 배열의 범위, 배열에서 가장 큰 원소

위 방법으로 올바른 수열인지 확인 한 후

현재 원소(arr[i])가 top보다 큰 경우, top이 arr[i]이 될 때까지 push(+), 그리고 현재 원소를 출력 pop

가장 큰 수(N)이 출력된 이후는 Stack에서 꺼내는 경우 밖에 없다. 따라서 남은 수 만큼 pop(-) 출력

저는 이렇게 생각하면서 알고리즘을 짜보았는데, 84%에서 틀렸습니다. 확인한 반례는 모두 만족했는데, 다른 예외적인 조건같은 것이 있을까요?

#include <iostream>

using namespace std;

bool IsAlright(int arr[], int N){
    int i = 0, j, top;
    //Loop until the biggest Number = N is biggest Num
    while(i < N && arr[i] <= N){
        //top is max number until now
        top = arr[i];
        //next number is less than top. then is must be descending!
        for(j = i + 1; j < N && arr[j] < top; j++)
            if(arr[j-1] < arr[j]) return false;
        i = j;
    }
    //After The biggeset number, Descending...
    for(; i < N; i++)
        if(arr[i-1] < arr[i]) return false;
    //All pass
    return true;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int arr[100000], N, i = 0, top = 0;
    
    cin >> N;
    
    while(i < N) { cin >> arr[i++]; }
    
    //Check Stack Numbers is possible?
    if(IsAlright(arr, N)){
        i = 0;
        while(i < N && arr[i] <= N){
            if(arr[i] > top){
                for(int j = top; j < arr[i]; j++)
                    cout << "+\n";
                top = arr[i];
            }
            //Pop Current Number
            cout << "-\n";
            i++;
        }
        //After The Biggest Number then pop all number!!
        while(i < N){
            cout << "-\n";
            i++;
        }
    }else{
        cout << "NO\n";
    }
    return 0;
}

zenith82114 2년 전 2

반례입니다.

8
4 2 5 6 8 7 3 1 
// this sequence is NOT alright

chackcooking 2년 전 0

아 숫자를 건너뛰는 경우에, 안되는 경우가 생기네요. 조건을 더 생각해봐야겠습니다. 감사합니다

댓글을 작성하려면 로그인해야 합니다.