[코딩테스트 일지 - 99클럽] 19일차 - Minimum Add to Make Parentheses Valid

코딩 테스트 준비 일지 19 일차

• 응시 사이트 : LeetCode

• 문제 : Minimum Add to Make Parentheses Valid

• 난이도 : 하

• 풀이시간 : 1h 11m

A parentheses string is valid if and only if:

• It is the empty string,

• It can be written as AB (A concatenated with B), where A and B are valid strings, or

• It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

Constraints:

• 1 <= s.length <= 1000

• s[i] is either '(' or ')'.

문제 풀이 접근

금일 문제 풀이 키워드는 String, Stack 이었는데, 괄호를 어떻게 최단움직임으로 완벽하게 쌍을 맞춰주냐 그게 핵심 문제였다.

크게 생각할 것은 없고, 문제를 2가지 방법을 생각했는데,
1. String 의 s[i] , s[i-1] 의 '(' ,')' 일 경우를 체크해서 answer를 하나 올리고 추후 연산에 넣는다.
2. Stack을 이용하여 '(' 일 경우 Push 하고, 가지고 있는 '(' 를 그다음 s[i] 가 ')' 괄호가 온다면 하나씩 Pop 해주는 것이다.

1번의 경우 여러 TC에서 막힐 소지가 있었다. 루프 카운터가 넘어가거나 하는 경우는 체크할 수 없기 때문이다.
2번의 경우가 Stack의 LIFO 성격을 이용해 하나씩 빼고 Answer + stack.Count() 를 더하면 원하는 값이나온다. ( 이 방법을 사용한다면, 사실 꼭 Stack을 이용하지 않아도 된다. )

정답 작성 코드 (C#)

public class Solution
    {
        public int MinAddToMakeValid(string s)
        {
            int answer = 0;

            if (s == string.Empty)
                return answer;

            Stack<char> stack = new Stack<char>();

            for(int i  = 0; i < s.Length; ++i)
            {
                if (s[i] == '(')
                    stack.Push(s[i]);

                if(stack.Count() <= 0 && s[i] == ')')
                {
                    ++answer;
                }

                if(stack.Count() > 0 && s[i] == ')')
                {
                    stack.Pop();
                }
            }

            return stack.Count()+ answer;
        }
    }

코드 결과