코딩테스트 준비 - Valid Parentheses

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : LeetCode

• 문제 : Valid Parentheses

• 사용언어 : C#

• 난이도 : 하

• 풀이시간 : 33m

• 유형 : 스택, 문자열
  

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104

• s consists of parentheses only '()[]{}'.

문제 풀이 접근

이 문제는, 여러 케이스를 생각해서 이렇게 풀었는데, 케이스 바로나왔으면 10분만에 풀었을 것 같다.
헷갈렸던 점은,
1. '(' 가 나오면 무조건 뒤에 ')' 나오도록 하는가?
2. 속괄호가 없을까? [()] 이런거..
1,2번이 모두 참이고 맞다면 문제는 10분도 필요없다 5분컷인데, s[index] ,s[index+1] 해서 비교하면 되는거라.. 해보니까 속괄호도 있고, 처음에 닫힌 브라킷으로 주는 경우도 있고해서 여러 예외가 필요했다.

문제 해결 플로우는,
1. 여는 브라킷 ' ( ' , ' [ ' , ' { ' 등이 나오면 Stack에 Push한다.
2. 이후 닫는 브라킷 ' ) ' , ' ] ' , ' } ' 이 나오면 Peek 으로 체크하고 Pop 한다.
3. 이 모든 과정을 수행해서 짝이 맞는다면 Stack 은 비어있는게 정상. 남아있다면 어딘가 닫히는게 없거나, 열리는게 없는데 닫히는 문자를 가져오거나 둘중하나. 고로 false 다.

정답 작성 코드 (C#)

using System.Collections.Generic;

public class Solution {
        public bool IsValid(string s)
        {
            bool answer = false;
            Stack<Char> st = new Stack<Char>();

            if ((s.Length == 0) || (s[0] == ')') || (s[0] == '}') || (s[0] == ']'))
                return false;


            for (int i = 0; i < s.Length; ++i)
            {
                var elem = s[i];

                if (elem == '(' || elem == '{' || elem == '[')
                {
                    st.Push(elem);
                    continue;
                }

                if (elem == ')' || elem == '}' || elem == ']')
                {
                    char sElem;

                    if(st.Count == 0)
                        st.Push(elem);

                    sElem = st.Peek();

                    if (sElem == '(' && elem == ')')
                    {
                        st.Pop();
                        continue;
                    }

                    if (sElem == '[' && elem == ']')
                    {
                        st.Pop();
                        continue;
                    }

                    if (sElem == '{' && elem == '}')
                    {
                        st.Pop();
                        continue;
                    }

                    break;
                }
            }

            answer = st.Count == 0 ? true : false;

            return answer;
        }
}

코드 결과

1,2 번 가설 테스트 코드 (C#) - 실패

public class Solution {
    public bool IsValid(string s) {

        for(int i = 0; i < s.Length-1; ++i)
        {
            var elem = s[i];
            var elemNext = s[i+1];
            
            if((elem == '(') && (elemNext == ')') == false)
                return false;
            
            if((elem == '[') && (elemNext == ']') == false)
                return false;
            
            if((elem == '{') && (elemNext == '}') == false)
                return false;
        }
        
        return true;
    }
}