백준 1662번 압축

문제 링크입니다: https://www.acmicpc.net/problem/1662

1662번: 압축

자소서 쓰느라 바빠서 오랜만에 포스팅하네요.

같은 학회원 분이 질문을 하셨던 문제라 풀어봤던 문제였습니다.

이 문제의 핵심은 먼저 괄호의 쌍의 위치를 전처리를 통해 파악하고 재귀함수를 통해 길이를 구하는 것이었습니다.

 

	#include <iostream>
	#include <string>
	#include <stack>
	using namespace std;
	const int MAX = 50;
	string s;
	int visited[MAX];
	int func(int start, int end)
	{
	int result = 0;
	for (int i = start; i < end; i++)
	{
	if (s[i] == '(')
	{
	int K = s[i - 1] - '0';
	result += K * func(i + 1, visited[i]) - 1;
	i = visited[i];
	continue;
	}
	result++;
	}
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	stack<int> st;
	// 괄호 쌍 인덱스 전처리
	for (int i = 0; i < s.length(); i++)
	{
	if (s[i] == '(')
	{
	st.push(i);
	}
	else if (s[i] == ')')
	{
	visited[st.top()] = i;
	st.pop();
	}
	}
	cout << func(0, s.length()) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~