[백준/BOJ] 4949번 : 균형잡힌 세상, 17298번 : 오큰수 (스택)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 4949번 : '균형잡힌 세상', 17298번 : '오큰수' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당하며 문제를 풀이하기 위해 스택에 대한 이해가 필요합니다.

 

 

4949번 : 균형잡힌 세상

 

대괄호와 소괄호가 적절히 열고 닫혔는지를 검사하는 문제입니다.

단순 괄호 여닫이만 따지면 안되고, 대괄호가 닫히기 전에 소괄호가 닫히거나, 소괄호가 닫히기 전에 대괄호가 닫히면 안됩니다.

따라서 스택을 써서 문제를 풀어주는 것이 가장 바람직합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        string str; getline(cin, str);
        if(str == ".") break;

        stack<char> Stack;
        bool check = true;
        for(int i=0; i<str.size(); i++) {
            if(str[i] == '[' || str[i] == '(') Stack.push(str[i]);
            else if(str[i] == ']') {
                if(Stack.empty()) check = false;
                else if(Stack.top() == '[') Stack.pop();
                else if(Stack.top() == '(') check = false;
            }
            else if(str[i] == ')') {
                if(Stack.empty()) check = false;
                else if(Stack.top() == '[') check = false;
                else if(Stack.top() == '(') Stack.pop();
            }
        }

        if(Stack.empty() && check) cout << "yes\n";
        else cout << "no\n";
    }
}

 

이 문제를 풀면서 깨달았는데 getline 함수를 위와 같이 써주면 버퍼 크기를 따로 잡아주지 않아도 공백 포함 줄 입력을 받을 수 있습니다.

나머지 구현은 스택으로 코드를 작성해주면 됩니다.

괄호에 해당하는 문자만 스택에 넣어서, 만약 top에 [가 있는데 )가 입력되거나, (가 있는데 ]가 입력되는 경우 check = false로 바꿔주어서 기록할 수 있습니다.

 

코드 속도를 더 올리고 싶다면 check = false로 바뀌는 시점에서 즉시 break를 사용해주시면 됩니다.

(그러면 안되겠지만 저는 코드의 가독성을 높이기 위해 효율성을 낮춰서 풀었습니다.)

 

 

 

 

17298번 : 오큰수

 

수열에서 오른쪽에 있으면서 더 큰 수 중 가장 왼쪽에 있는 수를 오큰수라고 할 때, 각 수의 오큰수들을 찾아 출력해주는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];

    stack<int> Stack;
    vector<int> ans(N);
    for(int i=N-1; i>=0; i--) {
        while(!Stack.empty() && arr[i] >= Stack.top())
            Stack.pop();

        if(Stack.empty()) ans[i] = -1;
        else ans[i] = Stack.top();

        Stack.push(arr[i]);
    }

    for(int i=0; i<N; i++) cout << ans[i] << " ";
}

 

이 문제는 스택으로 해결할 수 있는데, 수열의 오른쪽에서부터 역순으로 스택에 넣으면서 현재 수보다 스택의 top에 있는 수가 더 작거나 같으면 pop해서 더 큰 수가 나올 때까지 반복하는 방식으로 오큰수를 찾을 수 있습니다.

각 수에 대해서 탐색을 끝낸 이후에는 stack의 top에 현재 수를 넣기 때문에, 어떤 수의 오른쪽에 있는 수들 중에서 가장 왼쪽에 있는 수부터 검사가 되는 것입니다.

 

문제를 보고 바로 stack을 떠올리기는 쉽지 않으나 떠올리고 나면 스택을 유용하게 활용할 수 있는 좋은 문제라고 생각합니다.