[문제 링크]



문제 의도는 스택으로 푸는 문제이지만, 굳이 스택으로 풀지 않아도 되는 문제이다.


그냥 레이저를 만났을 때, 여는 괄호의 갯수 만큼 더해줘도 되지만, 여기서는 스택을 이용해서 풀어보겠다.





이 문제를 풀기 위해선, 닫는 괄호가 나타났을 때, 이 것이 레이저인지, 아니면 파이프의 끝을 나타내는 것인지 구별해야 된다.

구별하는 방법은 정말 쉽다, 닫는 괄호가 나타났을 때, 바로 전 문자를 체크해서 이게 여는 괄호인지 아닌지만 확인하면 된다.

즉 여는 괄호를 만나면 전부 스택에 push하다가, 닫는 괄호를 만나면 스택에서 pop하고 괄호가 레이저면 스택 사이즈만큼 더해주거나, 파이프 끝이면 1만 더해주면 된다.


위 사진으로 예를 들어보자. 

처음에 '('를 만나서 스택에 push한다, 그리고 두번째에 ')'를 만난다. 스택에서 '('를 pop한다. 이전 문자는 '('이므로 레이저이다. 결과값에 스택 사이즈(0)만큼 더해준다.

result += 0


그다음 '('를 4개 만난다. 스택에 '('가 4개 들어가고 스택 사이즈는 4이다. ')'를 만나서 스택을 pop한다. 바로 전이 '('이므로 이는 레이저이다. 결과값에 스택 사이즈(3)만큼 더해준다.

result += 3


바로 다음에 괄호를 다시 여닫고 스택을 그에따라 push,pop해준다. 레이저이므로 스택 사이즈(3)을 다시 더해준다.

result += 3


닫는 괄호를 만난다. 바로 전 문자는 ')'이므로 레이저가 아닌 파이프의 끝이다. 파이프 꼭다리가 남으므로 1을 더해준다.


result +=1


위의 방법을 계속 반복하면 된다. 나머지는 직접 해보자.



이를 구현한 코드는 다음과 같다.


#include <iostream>
#include <string>
#include <stack>
using namespace std;
string str;
int pipe(const string& str){
    stack<char> st;
    int result=0;
    for(int i =0; i<str.length();i++){
        //여는 괄호면 스택에 넣는다. 
        if(str[i]=='(') st.push(str[i]);
        //닫는 괄호면 이 괄호가 레이저인지, 파이프 끝인지 알아본다.
        else{
            st.pop();
            //레이저면 
            if(str[i-1]=='(') 
                result += st.size(); //잘린 갯수 추가. 
            //파이프의 끝이면 
            else result++; //닫혀서 잘려진 갯수 추가. 
        }
    }
    return result;
}
int main(){ 
    cin >> str;
    cout<<pipe(str);
}


스택을 사용하지 않는 방법은 그냥 여는 괄호나 닫는 괄호를 만날 때, 갯수만 체크해주면 된다. 위에서 스택 사이즈를 체크한 것 대신에 갯수만 따로 저장하는 것이라고 보면 된다.


'Algorithm > Problems' 카테고리의 다른 글

백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28
백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 9465 스티커  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15

+ Recent posts