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을 해준다.
이 또한 이해가 안된다면 그림을 보면 이해가 잘 될 것이다.
- 출처는 한국 정보 올림피아드이다.