백준 4889번 안정적인 문자열

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

4889번: 안정적인 문자열

DP를 이용하여 푼 문제였습니다. (다른 분들의 풀이를 확인해보니 굳이 DP를 쓸 필요 없이 쉽게 생각하면 되는 문제였습니다.)

 

알고리즘은 아래와 같습니다.

i) 짝이 지어지지 않은 왼쪽 괄호가 주어진 문자열 길이의 반 미만일 경우 idx 번째 문자를 왼쪽 괄호로 만들어줌으로써 하나 늘렸습니다.

ii) 짝이 지어지지 않은 왼쪽 괄호가 하나 이상 있을 경우 idx 번째 문자를 오른쪽 괄호로 만들어줌으로써 안정적으로 만들어줬습니다.

iii) 문자열의 마지막 문자가 확인했을 때 짝이 지어지지 않은 왼쪽 괄호의 수가 0이면 안정적인 문자열이고 0이 아니라면 불안정적인 문자열로 판단했습니다.

 

개발환경:Visual Studio 2017

 

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