[백준] 1874번 - 스택 수열 (실버 3)

문제

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

 

접근 방식

• 1~n 까지 오름차순으로 정렬된 num_vector, stack_vector, 원하는 수열을 입력 받을 target_vector 를선언한다.
• target_v의 각 요소들에서 num의 top(back)과 값을 비교한다.
• 같으면 다음 target으로 이동하고 다르면 하나씩 뽑아서 비교하면서 stack에 넣는다.
• 넣는 중에 찾을 경우 다음 target으로 이동한다.
• 다 넣고 못찾았을 경우 stack을 확인한다.
• stack에서 하나씩 빼면서 탐색한다.
• stack이 비었는데 target이 남아있거나 , 원하는 값을 찾을 수 없는 경우 No로 판단한다.

---

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, tmp, num_cur, flag;
    cin >> n;

    vector<int> num_v, stack_v, target_v;
    vector<char> res_v;

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        target_v.push_back(tmp);
        num_v.push_back(i + 1);
    }

    reverse(num_v.begin(), num_v.end());
    
    for (auto tmp_target : target_v) {
        flag = 0;

        if (num_v.size() == 0 && stack_v.size() == 0) {
            res_v.clear();
            break;
        }

        if (!stack_v.empty()) {
            if (tmp_target == stack_v.back()) {
                stack_v.pop_back();
                res_v.push_back('-');
                flag = 1;
                continue;
            }
        }

        while (true) {
            if (!num_v.empty()) {
                num_cur = num_v.back();
                stack_v.push_back(num_cur);
                res_v.push_back('+');
                num_v.pop_back();

                if (tmp_target == num_cur) {
                    stack_v.pop_back();
                    res_v.push_back('-');
                    flag = 1;
                    break;
                }
            }
            else {
                if (stack_v.empty())
                    break;

                while (!stack_v.empty()) {
                    if (tmp_target == stack_v.back()) {
                        stack_v.pop_back();
                        res_v.push_back('-');
                        flag = 1;
                        break;
                    }
                    else {
                        stack_v.pop_back();
                    }
                }
                
                if (!flag) {
                    res_v.clear();
                    break;
                }
            }
        }
    }


    if (res_v.empty()) {
        cout << "NO\n";
    }
    else {
        for (auto tmp_res : res_v) {
            cout << tmp_res << "\n";
        }
    }
    
    return 0;
}

---

 

결과