백준 10799번 쇠막대기

문제 링크입니다: https://www.acmicpc.net/problem/10799

분류는 스택 알고리즘으로 되어있지만 굳이 스택을 이용하지 않아도 되는 문제였습니다.

알고리즘은 아래와 같습니다.

1. '(' 다음에 바로 ')'가 나올 경우는 파이프가 아니고 레이저이므로 prev를 통해 이전 괄호의 모양을 저장합니다.

2. 레이저를 제외하고는 전부 파이프이므로 '('가 나올 때마다 pipe를 증가시킵니다.

3. 레이저가 나올 경우 여태까지 누적 pipe 개수만큼 잘리므로 결과에 pipe 개수만큼 증가시킵니다.

4. 레이저가 아닌데 ')'가 나올 경우 파이프의 끝이므로 pipe 개수를 감소시키고 결과를 하나 증가시킵니다.

-> 마지막 레이저에 잘린 뒤 남은 부분이므로 결과를 하나 증가시킵니다.

5. 1번 ~ 4번을 끝까지 반복합니다.

#include <iostream>

#include <string>

using namespace std;

 

int main(void)

{

        string s;

        cin >> s;

 

        int pipe = 0, result = 0;

        char prev;

 

        for (int i = 0; i < s.length(); i++)

        {

                 //파이프 시작

                 if (s[i] == '(')

                         pipe++;

                 else

                 {

                         pipe--;

                         //레이저

                         if (prev == '(')

                                 result += pipe;

                         //파이프 끝

                         else

                                 result++;

                 }

                 //기존 괄호 저장

                 prev = s[i];

        }

        cout << result << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~