[algorithm] balanced brackets (균형잡힌 괄호)

https://programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

 

 

알고리즘 문제중 주어진 문자열의 괄호가 제대로 닫히는 괄호쌍인지를 확인하는 경우가 있다.

EX) (()()) , ((())(()) = True, False

 

 

이 때는 보통 Stack 을 활용하지만, stack이 아니어도 균형 여부를 구할 수 있다.

1. ( 가 읽힌다면, left 변수를 더한다
2. ) 가 읽힌다면, left 변수를 1 뺀다
3. 읽은 뒤 left 가 음수면, False
4. 문자열의 문자를 모두 순회한 뒤 left = 0 이면 True다

private boolean isPerfect(String w) {
    int left = 0;
    for(char c : w.toCharArray()) {
      if (c == '(') {
        left++;
      } else if (c==')') {
        left--;
      }
      if (left < 0) {
        return false;
      }
    }
    return true;

위 코드는, (, ) 의 수가 같을 때 유효하다.