[프로그래머스] 쇠막대기

문제: https://programmers.co.kr/learn/courses/30/lessons/42585

오늘은 프로그래머스 [스택/큐] 문제 중 쇠막대기를 소개할까 한다.

사실 이건 백준에서도 풀었었던 문제인데

여기에도 있어서 반가워서 포스팅 할려고 한다.

문제는 '(' 와 ')' 로 이루어진 문자열이 주어졌을 때

최종적으로 쇠막대기가 몇 개로 나누어 지는지 물어보는 문제이다.

만약 '( )' 처럼 괄호의 열림과 닫힘이 연속적으로 주어진다면

레이저를 쏘아서 현재 놓여져 있는 쇠막대기를 나눌 수 있다.

문제푸는 아이디어는 스택/큐 문제이지만

굳이 스택/큐를 사용할 필요는 없다.

간단한 규칙찾기로도 이 문제를 해결할 수 있다.

문제에도 있는 예제인

( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) ) 로 설명하겠다.

이것만 기억하면 된다.

1. '( )'는 레이저를 쏘아서 현재 놓여져 있는 쇠막대기를 나눈다. => 즉, 레이저의 위치에 놓여진 쇠막대기만큼 개수 추가

2. 홀로 사용 된 '('의 의미는 하나의 쇠막대기를 추가해서 놓는 것.

3. 홀로 사용 된 ')'의 의미는 하나의 쇠막대기 길이가 끝난 것.

현재 놓여진 쇠막대기 개수를 cnt, 최종적인 쇠막대기 개수를 res라고 정의하고 예제를 순서대로 진행해 보겠다.

( => cnt++;            cnt = 1, res = 0

) => 바로전 '('이었으므로 레이저이다. cnt--, res += cnt;            cnt = 0, res = 0

                                  레이저일 땐 '('가 쇠막대기를 의미하는 것이 아니므로 위에서 '('로 인해 더해진 cnt를 하나 뺀다.

( => cnt++;            cnt = 1, res = 0

( => cnt++;            cnt = 2, res = 0

( => cnt++;            cnt = 3, res = 0

( => cnt++;            cnt = 4, res = 0

) => 레이저. cnt--, res += cnt;            cnt = 3, res = 3

( => cnt++;            cnt = 4, res = 3

) => 레이저. cnt--, res += cnt;            cnt = 3, res = 6

) => 쇠막대기 하나의 길이가 끝남. 끝난 쇠막대기의 마지막 조각을 더해준다. cnt--, res++;            cnt = 2, res = 7

( => cnt++;            cnt = 3, res = 7

( => cnt++;            cnt = 4, res = 7

) => 레이저. cnt--, res += cnt;            cnt = 3, res = 10

) => cnt--, res-++;            cnt = 2, res = 11

( => cnt++;            cnt = 3, res = 11

) => 레이저. cnt--, res += cnt            cnt = 2, res = 13

) => cnt--, res++;            cnt = 1, res = 14

) => cnt--, res++;            cnt = 0, res = 15

( => cnt++;            cnt = 1, res = 15

( => cnt++;            cnt = 2, res = 15

) => 레이저. cnt--, res += cnt            cnt = 1, res = 16

) => cnt--, res++;            cnt = 0, res = 17

이렇게 마지막까지 도달했을 때 cnt는 0이 되어야 모든 쇠막대기를 처리한 것이다.

추가적으로 어떻게 이렇게 해도 되는지가 궁금할 수 있는데

이 문제의 조건인

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.
- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.
- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.
- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

위의 네 가지 조건 덕분에 가능하다.

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.

=> 먼저 생긴 '(' 가 가장 길다. 덕분에 열고 닫는 괄호의 개수와 순서는 짝을 이룬다. ( ( ( ) ) ) 즉, '('마다 cnt++을 해주어도 되는 것이다.

- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.

=> 중요한 점은 끝점이 겹치지 않는다는 점이다. 이 조건 덕분에 닫힌 괄호가 하나 생겼을 때 cnt--, res++을 해도 문제가 없는 것이다.

- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.

=> 마지막까지 진행했을 때 cnt가 0으로 끝날 수 있는 조건이다.

- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

=> 레이저를 쏘았을 때 cnt--, res += cnt를 할 수 있는 이유다. 레이저가 쇠막대기와 겹치는 경우가 없기 때문에 마음 편히 cnt를 더해줄 수 있는 것이다. 

끝.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    int cnt = 0;
    int res = 0;
    for(int i=0; i<(int)arrangement.size(); i++){
        if(arrangement[i] == '('){
            cnt++;
        }else{
            if(arrangement[i-1] == '('){
                cnt--;
                res += cnt;
            }else{
                res++;
                cnt--;
            }
        }
    }
    answer = res;
    return answer;
}