Gidhub BE Developer

[Programmers] 쇠 막대기

2018-09-27
goodGid

Problem

Problem URL : 쇠 막대기


[1] Answer Code (18. 09. 27)

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#define p pair<int,int>
using namespace std;

int solution(string arrangement) {
    int answer = 0;
    stack<p> s;
    int size = (int) arrangement.size();
    for(int i=0; i<size; i++){
        if(arrangement[i] == '('){
            s.push(p(i,1));
        }
        else{
            if(s.top().first == i-1){
                s.pop();
                answer += s.size();
            }
            else{
                s.pop();
                answer += 1;
            }
        }
    }
    
    return answer;
}

Review

  • Stack 자료구조를 사용해 풀이했다.

  • 로직은 간단하다.

  • ’(‘가 들어오면 push

  • ’)’가 들어오면 2가지 경우로 나눈다.

1. 바로 이전에 '(' 일 경우 (= stack.top()의 index가 현재 체크하는 index-1일 경우)
그렇다면 stack.pop()을 해준다.
즉 이전에 '('는 쇠 막대기가 아닌 레이저이다.
그리고 남은 stack의 size만큼 더해준다.
이해가 안된다면 그림을 보면 이해가 잘 될 것이다.

2. 바로 이전에 '(' 가 아닐 경우 (= stack.top()의 index가 현재 체크하는 index-1가 아닐 경우 )
이 경우에 '('의 의미는 자석이다.
그렇기 때문에 단순히 answer에 +1을 해준다.
이 또한 이해가 안된다면 그림을 보면 이해가 잘 될 것이다.

Recommend

Index