250310 - 백준 1874 스택 수열

솔룩스 면접을 보면서 나랑 비슷하거나 학번이 조금 더 높으신 분들이 나에 비해 상당히 많은 것들을 이뤄놓으셨어서 현타가 많이 왔다

 

생각해보니까 365일이면 하루에 1개씩만 올려도 내가 365개의 공부를 한다

 

일단.. 고민할 시간에 하는게 빠름

전공, 책 등등 공부한 내용을 적겠다

오늘은 운영진 회의 있었어서 백준 푼걸 적겠다

 

1. 스택

선입선출, 아래에서 위로 쌓이는 구조

#include <stack>

stack<int> s;

 

2. 문제 접근

일단 입력 받는 순서대로 벡터에 저장 -> for문으로 모든 벡터 요소들에 대해 접근할 수 있도록 구현

flag 라는 변수 사용 -> 1부터 N까지 숫자 증가시키면서 스택에 넣는 용도

따라서 while 문 조건은 flag 가 N보다 작거나 같을 때까지!

 

계속 -11 ? 뭐 이런 오류가 떴는데 s.top() 이나 s.pop() 을 할 때 스택이 비어있지 않은지 꼭 확인해주는게 스택에서는 중요하다는걸 잊었다

그래서 스택이 비어있지 않고 && 내가 찾는 값이 스택의 최상단에 있을 때 -> pop -> 다음 v[i] 로 이동

최상단이 아니라 쌓여야할 때 -> flag++ 값을 push

 

제일 헷갈렸던 부분인데, flag == N+1 즉 모든 숫자(1~N) 가 스택에 한 번씩 다 들어간 이후에 이제 pop만 남았을 때였는데

마찬가지로 스택이 비어있지 않고, 최상단 값이 찾는 값과 같으면 pop 해가면서 지웠다

 

결국 스택이 비어있으면 수열을 만들 수 있다는 뜻이므로 a[i] 출력,

안 비어있으면 NO 출력

 

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int N;
    vector<char> a;
    vector<int> v;
    stack<int> s;
    cin >> N;

    int input;
    for(int i=0;i<N;i++){
        cin >> input;
        v.push_back(input);
    }

    int flag = 1;
    for(int i=0;i<N;i++){
        while(flag <= N){
            if(!s.empty() && v[i] == s.top()){
                //cout << s.top() << "t" << flag << "\n";
                s.pop();
                a.push_back('-');
                break;
            }
            else{
                s.push(flag++);
                a.push_back('+');
            }
        }
        if(flag == N+1){
            if(!s.empty() && v[i] == s.top()){
                s.pop();
                a.push_back('-');
            }
        }
    }
    
    if(s.empty()){
        for(int i=0;i<a.size();i++){
            cout << a[i] << "\n";
        }
    }
    else{
        cout << "NO";
    }
    
    return 0;
}

 

3. 주의할 점

- 스택에서 top() 이나 pop() 할 때는 비어있는지 꼭 확인하자

- NO 인데 No 라고 써서 틀렸다^^.. 눈을 크게 뜨자

- 자료형이 char 이면 작은따옴표 쓰기 ''