JArchive 프로그래밍 일기

문제

스택 수열 백준 1874번

리뷰

문제 맨 밑에 '힌트'를 읽고 이해 했다.

1부터 n 까지 수에 대해서는 반드시 push n번, pop n번이 수행되야 목표수열을 얻을 수 있다.

만약, 스택에 숫자가 남아있으면, 실패니까 "NO" 를 출력해야 한다.

1부터 n 까지 수를 차례로 push 한다.

for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다. 

        st.push(i);
        answer.push_back('+');
}

그러나 pop을 하려면 스택의 top이 목표수열의 숫자와 일치하는지 계속 확인해줘야 한다. 그래서 while문으로 만들었다.

pop을 할 때는 목표 수열의 다음숫자를 타겟으로 해야하니까 목표수열의 인덱스도 증가시켜줘야 한다는게 중요하다.

스택이 비어있으면 pop도 불가하니까, empty() 함수로 스택이 비었는지 확인한다.

for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다. 

        st.push(i);
        answer.push_back('+');

        while(!st.empty() && (st.top() == N[idx])){ // 수열의 숫자와 같으면, pop

            st.pop();
            answer.push_back('-');
            idx++; // 목표 수열의 인덱스도 증가시켜준다. 
        } 

}

예를 들어, 입력받은 수열크기는 8이다. 목표 수열은 4 3 6 8 7 5 2 1 이다.

목표 수열은 4 3 6 8 7 5 2 1 이다.  (현재는 idx = 0, N[idx] = 4 를 타겟으로 한다. )

1, 2, 3, 4 순으로 push 했다. (위의 코드로 보면 i가 4까지 진행된 상태다)

여기서 목표수열의 첫번째 숫자 4와 스택의 top 4 가 같아진다. 즉, while 문의 조건을 충족한다. 
pop 한다. 
목표수열의 다음 숫자 3 과 스택의 top 3이 또 같아진다.  
(idx = 1로 바뀌면서 N[idx] = 3 이 된다. )
pop 한다. 

다시 5, 6 순으로 push 한다. 
while 문의 조건을 다시 확인한다. 

**코드

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int N[100001]; // 입력받은 수열  
vector<char> answer; // 출력할 +, - 담을 벡터  
stack<int> st;

int main(void){

    freopen("input.txt", "rt", stdin);

     int i, idx, num = 0;

     scanf("%d", &num); // num 이하의 수열을 입력받자. 

    for(i=0; i<num; i++){ // 목표 수열 입력받기 
        scanf("%d", &N[i]); 
    }  // 입력받기 끝  


    // answer에는 push 할 때 '+'를 넣고, pop 할 때 '-'를 넣는다.  

    for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다. 

        st.push(i);
        answer.push_back('+');

        while(!st.empty() && (st.top() == N[idx])){ // 수열의 숫자와 같으면, pop

            st.pop();
            answer.push_back('-');
            idx++; // 목표 수열의 인덱스도 증가시켜준다. 
        } 

    }

    if(!st.empty()) printf("NO"); // 스택에 뭐가 남았다면 실패니까 "NO"
    else{
        for(i=0; i<answer.size(); i++){ // answer 에 담았던 문자들 순차출력 
            printf("%c\n", answer[i]);
        }   
    } 

     return 0;
}