---
layout: post
title:  " [Programmers] 42585. 쇠 막대기 "
categories: Algorithm
tags: Programmers reSolve
author: goodGid
---
* content
{:toc}

## Problem 
Problem URL : **[쇠 막대기](https://programmers.co.kr/learn/courses/30/lessons/42585)**








---

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

``` cpp
#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을 해준다.
이 또한 이해가 안된다면 그림을 보면 이해가 잘 될 것이다.
```

* 출처는 [한국 정보 올림피아드](https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do)이다.

Write PGM Post " 42585. 쇠 막대기 "
Write PGM Post " 42585. 쇠 막대기 "
