문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

풀이

문자열 문제들의 키포인트는 어떤 기준으로 문자열을 분리/재배치/삭제/추가해 정답을 도출할 것인가와, 해당 과정에서 시간복잡도가 가장 낮은 방법을 찾아내는 것이다.

이 문제의 경우, '{' 뒤엔 반드시 '}'가 와야 한다는 규칙에 집중하면 쉽게 해결이 가능하다.

1. 반드시 존재하는 최소단위의 한 쌍'{}'을 찾아 소거시키다 보면 모든 '{}'가 소거될 것이다.
2. 올바른 괄호라면 하나의 '{'뒤에는 반드시 하나의 '}'가 보장될 것이므로, '{'의 개수와 '}'의 개수는 반드시 같을 것이다.

1번의 경우, 결국 길이가 n인 문자열에 대한 순회를 최대 1/2n 번 반복 해야 한다. 따라서 O(n^2)
2번의 경우 문자열 길이만큼 순회만 하면 끝나기 때문에 O(n)

public bool solution(string s)
        {
            int cnt = 0;
            foreach (char word in s)
            {
                if (word == '(')
                    cnt++;
                else if (word == ')')
                    cnt--;

                if (cnt < 0)
                    return false;
            }

            return cnt == 0;
        }