C++ 백준 10799 쇠막대기

백준 10799

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

10799번: 쇠막대기

 

풀이 전 내 생각

 

우선 쇠막대기가 무엇을 의미하는지 고민을 하면 쉽게 풀리는 문제다.

그림을 보면 쇠막대기의 길이는 괄호가 시작하고 끝나는 부분을 뜻한다.

그럼 여러개의 괄호 생명주기가 생성되고 '()' 라는 레이저를 쏜다는 의미는 현재까지 쌓여있는 괄호 생명주기의 개수

를 의미한다. 예를 들어 -> 방향 기준으로  '((()' 는 괄호 생명주기의 시작인 '('가 레이저 전까지 2개 존재한다. 그래서 레이저를 쏘게 되면 2개의 쇠막대기를 획득한다. 사실 레이저도 엄연한 괄호이기 때문에 '(' 부분까지 총 3개 이지만 레이저 특성 상 바로 ')' 로 닫혀 생명주기가 끝나기 때문에 개수로 치지 않는다.

 

풀이는 스택 형식인 FIFO 선입선출의 방식으로 진행하여 해결했다. 풀이의 포인트는 ')' 괄호가 올 때는 이전 값이 무엇이든 ')'개수가 증가하기 때문에 '(' 가 현재 값일 때만 조건을 걸면된다. 이전 값이 '(' 이며 현재 값도 '(' 이면 단지 하나의 괄호 생명주기가 끝난 것이기 때문에 총 개수를 1 증가시켜준다. 이전 값이 ')'인데 현재 값이 '(' 이면 레이저를 쏜 것이기 때문에 현재 까지 쌓인 ')'의 개수를 레이저 괄호 개수를 감소하고 증가시켜준다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	char cur;
	vector<char>vec;
	int rCnt = 0;
	int lCnt = 0;
	int sum = 0;
	char prev = ' ';
	while ((cur = getchar()) != '\n')
	{
		vec.push_back(cur);
	}

	for (int i = vec.size() - 1; i >= 0; i--)
	{
		char comp = vec[i];

		if (prev == '(' && comp == '(')
		{		
			rCnt--;
			sum += 1;
			prev = comp;
		}

		else if (prev == ')' && comp == '(')
		{
			rCnt--;
			sum += rCnt;		
			prev = comp;
		}

		else {
			rCnt++;
			prev = comp;
		}

		vec.pop_back();
	}

	cout << sum;
}