백준10799 쇠막대기

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/10799

문제 출처

  • 2015 KOI 지역 본선 초등부3, 중등부2

사용 알고리즘

  • 스택

시간복잡도

  • O(n)

풀이

쇠막대기의 양 끝은 ( 와 ) 로 이루어져있고, 레이저가 지나가는 줄은 () 로 표현됩니다.

이 그림에서 파란 배경의 괄호는 레이저가 지나가는 지점이고, 나머지 괄호는 같은 색끼리 짝입니다.

가장 먼저, 정답을 저장할 변수를 선언한 뒤, 0으로 초기화합니다.
일단 현재 글자가 ( 이면 stack에 넣습니다.

만약 현재 글자가 ) 이면 두 가지의 경우로 나뉘게 됩니다.

  • 이전 글자가 ( 이면 이전 글자 + 현재 글자가 () 이 되므로 레이저가 지나가는 자리입니다.
    그러므로, stack에서 ( 를 하나 빼주고 현재 위치에 존재하는 쇠막대기의 개수 만큼을 정답을 저장할 변수에 더해줍니다.
  • 만약 이전 글자가 ( 가 아니라면, 현재 위치에 있는 괄호는 쇠막대기의 오른쪽 끝을 나타내므로 정답을 저장할 변수를 1 증가 시키고(철근은 n번 잘리면 n+1개가 됩니다.),
    stack에서 하나를 pop해줍니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

stack<int> s;
int ans = 0;

int main(){
    char str[100100];
    int len;
    scanf("%s", str);
    len = strlen(str);
    for(int i=0; i<len; i++){
        if(str[i] == '(') s.push(1);
        else{
            if(str[i-1] == '('){
                s.pop();
                ans += s.size();
                //s.pop();
            }
            else{
                s.pop();
                ans++;
            }
        }

    }
    printf("%d", ans);
}