[Algorithm] 3주차 스터디 - 스택(백준 17608, 10828, 2504)

알고리즘 스터디 3주차에는 선형 자료구조인 스택을 공부하고 스택 관련 문제들을 풀어보았습니다.

 

17608 막대기

[문제 링크]

17608번: 막대기

 

[문제 요약]

높이가 각각 다른 막대기들을 왼쪽에서부터 오른쪽으로 일렬로 세웁니다. 그리고 나서 오른쪽에서 막대기들을 바라보면 오른쪽에 있는 막대기보다 높이가 낮은 막대기는 보이지 않습니다. N개의 막대기의 높이가 왼쪽에서 오른쪽으로 차례대로 주어지고, 오른쪽에서 바라봤을 때 보이는 막대기의 개수를 구하는 문제입니다.

 

 

[풀이]

스택에 왼쪽에서부터 차례대로 막대의 높이를 push합니다. 그리고 나서 오른쪽에서부터 차례대로 pop하며 pop한 막대기의 높이가 현재까지 pop한 막대기의 높이의 최댓값보다 클 경우, 보이는 막대기의 개수를 증가시켜주고 높이의 최댓값을 업데이트합니다.

 

 

[소스코드]

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int n;
    stack<int> s;
    
    scanf("%d", &n);
    
    while (n--) {
        int height;
        scanf("%d", &height);
        s.push(height);
    }
    
    int max_height = 0;
    int cnt_visible = 0;
    
    while (!s.empty()) {
        if (s.top() > max_height) {
            cnt_visible++;
            max_height = s.top();
        }
        s.pop();
    }
    
    printf("%d\n", cnt_visible);
    return 0;
}

 

---

 

10828 스택

[문제 링크]

10828번: 스택

 

[문제 요약]

정수를 저장하는 스택을 구현한 후에 push, pop, size, empty, top 명령어를 수행하는 프로그램을 작성하는 문제입니다. 

 

 

[풀이]

C++ STL의 stack을 사용하여 구현할 수 있습니다. stack의 push, pop, size, empty, top 멤버 함수를 사용하면 됩니다. 스택을 사용하며 할상 주의해야 할 점은 pop이나 top을 수행할 경우 꼭 스택이 비어있는지 확인하는 empty를 수행해야 합니다.

참고: www.cplusplus.com/reference/stack/stack/?kw=stack

stack - C++ Reference

 

[소스코드]

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    stack<int> s;
    while (n--) {
        string cmd;
        cin >> cmd;
        
        if (cmd == "push"){
            int num;
            cin >> num;
            s.push(num);
        }
        else if (cmd == "top") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
        }
        else if (cmd == "size") {
            cout << s.size() << '\n';
        }
        else if (cmd == "empty") {
            cout << s.empty() << '\n';
        }
        else if (cmd == "pop") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
            if (!s.empty()) {
                s.pop();
            }
        }
    }
    return 0;
}

 

---

 

2504 괄호의 값 

[문제 링크]

2504번: 괄호의 값

 

[문제 요약]

'(', ')', '[', ']' 의 네 개의 문자로 이루어진 괄호열을 입력받고 '올바른 괄호열'인지 검사하고 '괄호열의 값'을 구하는 문제입니다.

여기서 '올바른 괄호열'이란 다음 세 조건을 만족하는 괄호열을 말합니다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

올바른 괄호열이 아닐 경우 0을 출력하고 올바른 괄호열일 경우에는 '괄호열의 값'을 출력하는데, 괄호열의 값은 다음과 같이 구할 수 있습니다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

 

[풀이]

먼저 괄호열의 문자들을 왼쪽에서부터 차례대로 스택에 저장합니다. 스택에 저장하는 과정에서 열린 괄호('(', ')')를 만날 경우와 닫힌 괄호('[', ']')를 만날 경우에 대해 다른 처리를 해줍니다. 각각 어떤 처리를 할 것인지에 대해서는 괄호열의 몇 가지 성질에 대해 이해하면 더 쉽게 생각해낼 수 있습니다.

 

1. 올바른 괄호열은 항상 곱의 합으로 나타낼 수 있습니다.

예를 들면 (())은 2*2 로 나타낼 수 있고,

(()[])은 2 *(2 + 3) 즉, 2*2 + 2*3 으로 나타낼 수 있고,

[(())[()()]]은 3 * ( 2 * 2 + 3 * (2 + 2)), 즉 3*2*2 + 3*3*2 + 3*3*2 로 나타낼 수 있습니다.

 

2. 위에서본 곱의 합에서 곱들은 열린 괄호열을 만날 때마다 수행됩니다.

[(())[()()]]은 3*2*2 + 3*3*2 + 3*3*2 로 나타낼 수 있다고 했습니다. 각 곱들에 대해서 살펴보면 다음과 같이 대응된다는 것을 알 수 있습니다.

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

 

3. 닫는 괄호열을 만날 때마다 열린 괄호열을 상쇄시켜줍니다. 

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

노란색 부분을 계산할 때, 빨간색 부분에서 닫는 괄호열을 만나 이미 열린 괄호열을 만나면서 수행되었던 곱을 상쇄시켜 다시 나누어줄 수 있습니다.

 

4. 최종 결과값에 곱한 값을 합할 때는 '()’ 와 ‘[]’를 만날 때만 해주면 됩니다.

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

[(())[()()]] --> 3*2*2 + 3*3*2 + 3*3*2

각각의 빨강, 노랑, 파랑의 곱들은 민트색처럼 닫는 괄호열을 만났는데 이전의 문자열이 해당 괄호에 맞는 열린 괄호열일 때 지금까지 곱한 값들을 합해주면 됩니다.

 

 

[소스코드]

#include <iostream>
#include <stack>

using namespace std;

int main() {
    string input;
    cin >> input;
    
    int product = 1;
    int answer = 0;
    bool is_correct = true;
    stack<char> seq;
    
    for(int i = 0; i < input.length(); i++) {
        char bracket = input[i];
        if (bracket == '(') {
            seq.push('(');
            product *= 2;
        }
        else if (bracket == '[') {
            seq.push('[');
            product *= 3;
        }
        else if (bracket == ')') {
            if (seq.empty() || seq.top() != '(') {
                is_correct = false;
                break;
            }
            else {
                if (input[i - 1] == '(') answer += product;
                seq.pop();
                product /= 2;
            }
        }
        else {
            if (seq.empty() || seq.top() != '[') {
                is_correct = false;
                break;
            }
            else {
                if (input[i - 1] == '[') answer += product;
                seq.pop();
                product /= 3;
            }
        }
    }
    
    if (!is_correct || !seq.empty()) cout << "0\n";
    else cout << answer << '\n';
    
    return 0;
}