[백준/C++]#10799 - 레이저로 쇠막대기 자르는 문제

 

풀이

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    string a;
    int cnt = 0;
    cin >> a;
    stack<int> s;		// 스택 생성
        for (int i=0; i < a.size(); i++) {		// 문자열 크기만큼 반복
            if (a[i] == '(')		// '('가 들어오면 스택에 넣는다.
                s.push(a[i]);
            else {					// ')' 가 들어오는 경우
                if (a[i-1] == '(') {	// 이전에 '('가 들어왔다면 pop하고 스택의 크기를 cnt에 더해준다.
                	s.pop();
                    cnt+=s.size();
                }
                else {			// 그렇지 않다면 pop하고 cnt에 1을 더한다.
                	s.pop();
                    cnt++;
                }
            }
        }
    cout << cnt;
    return 0;
}

C++ 개념

C++에서는 stack 라이브러리를 받아서 스택을 구현할 수 있다.

stack은 LIFO 구조로, 자주 사용하는 함수는 push, pop, top, empty, size가 있다.

이번 문제에는 push(), pop(), size()를 사용했다.

---

풀이

'( )' 의 짝이 맞으면 레이저가 발사된다. 그리고 ( 무언가 ) 가 들어가 있는 경우 막대로 표현한다. 레이저가 막대를 끊을 때, 이전 '(' 의 개수만큼 막대가 끊기는 것을 볼 수 있다. '( )' 의 짝이 맞지 않으며 ')' 가 입력되는 경우 막대가 종료된다.

스택을 사용하는 이유는, 레이저로 막대가 끊길 때 이전 '(' 의 개수를 size()함수를 통해 나타내기 위함이다.

막대의 길이가 종료될 때, 마지막으로 남은 부분도 더해야하므로 +1을 한다.스택을 사용하는 이유는, 레이저로 막대가 끊길 때 이전 '(' 의 개수를 size()함수를 통해 나타내기 위함이다.

또한 막대의 길이가 끝날 때, 마지막으로 남은 부분도 더해야하므로 +1을 해야한다.

 

일단 for문을 사용해 문자열에서 각 문자를 가져온다.

'(' 일 때는 스택에 저장한다. 그리고 ')' 일 때의 경우는 두가지로 나눌 수 있다.

하나는 레이저일 때이고, 하나는 막대가 종료될 때이다. 이전에 입력된 문자가 '(' 인 경우 레이저이므로 if문을 사용해 나눈다.

---

+a

다른 방식으로 푼 경우의 소스코드이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    string a;
    int cnt=0;
    cin >> a;
    stack<int> s;
        for (int i=0; i < a.size(); i++) {
            if (a[i] == '(')
                s.push(i);
            else {
                if (s.top()+1 == i) {
                	s.pop();
                   	cnt+=s.size();
                }
                else {
                	s.pop();
                	cnt++;
                }
            }
        }
    cout << cnt;
    return 0;
}

이 경우엔 스택에 성분값이 대입된다. 그러한 성분값을 활용해 s.top()+1 == i 로 레이저를 구별한다.

이 문제에서는 a[i-1] = '(' 와 동일하게 사용되었지만, 조건이 조금 달라진다면 직전값을 stack의 top()을 통해 찾아내는 방법이 더 자주 쓰일 것 같다.