난이도 : Level 2
문제 출처

---

문제 이해

문자열 s가 주어졌을 때, 괄호가 올바르게 열리고 닫혀 있는지 판단하는 문제이다.

예를 들어 "()", "(())" 같은 경우는 올바른 괄호이므로 true를 반환하고, ")(", "(()" 같은 경우는 올바르지 않으므로 false를 반환해야 한다.

---

해결 아이디어

처음에는 다음과 같이 생각했다.

1. 문자열의 시작이 )라면 올바른 괄호가 아니다.
2. 문자열의 끝이 (라면 올바른 괄호가 아니다.
3. 여는 괄호 (는 +1, 닫는 괄호 )는 -1로 처리한다.
4. 순회 도중 값이 음수가 되면 닫는 괄호가 더 많이 나온 것이므로 false를 반환한다.
5. 모든 순회가 끝난 뒤 최종 값이 0이면 괄호의 짝이 맞으므로 true를 반환한다.

핵심은 괄호의 개수를 직접 세는 것이다.

(를 만나면 아직 닫히지 않은 괄호가 하나 생긴 것이므로 count += 1을 해주고,
)를 만나면 열린 괄호 하나를 닫는 것이므로 count -= 1을 해준다.

이때 count가 중간에 음수가 된다면, 여는 괄호보다 닫는 괄호가 먼저 많이 나온 상황이다.

예를 들어 다음과 같은 경우이다.

())(

이 경우는 전체 개수만 보면 여는 괄호 2개, 닫는 괄호 2개라서 개수는 같지만, 중간에 닫는 괄호가 먼저 초과되기 때문에 올바른 괄호가 아니다.

따라서 단순히 최종 개수만 보는 것이 아니라, 순회 중간에 count < 0이 되는지도 확인해야 한다.

---

내 코드

function solution(s) {
  let count = 0;

  if (s[0] === ")") {
    return false;
  } else if (s[s.length - 1] === "(") {
    return false;
  } else {
    for (const ch of s) {
      if (ch === "(") {
        count += 1;
      } else {
        count -= 1;

        if (count < 0) {
          return false;
        }
      }
    }
  }

  return count === 0 ? true : false;
}

파이썬 코드

def solution(s):
    count = 0

    if s[0] == ")":
        return False
    elif s[-1] == "(":
        return False
    else:
        for ch in s:
            if ch == "(":
                count += 1
            else:
                count -= 1

                if count < 0:
                    return False

    return count == 0

처음에는 문자열의 첫 번째 문자와 마지막 문자를 따로 검사했다.

다만 JavaScript에서는 Python처럼 s[-1]로 마지막 문자를 가져올 수 없다.
마지막 문자를 가져오려면 s[s.length - 1]을 사용해야 한다.

또한 count = 0처럼 선언 없이 쓰는 것보다, let count = 0처럼 명확하게 변수를 선언하는 것이 좋다.

---

더 깔끔한 코드

function solution(s) {
  let count = 0;

  for (const ch of s) {
    if (ch === "(") {
      count += 1;
    } else {
      count -= 1;
    }

    if (count < 0) {
      return false;
    }
  }

  return count === 0;
}

사실 처음과 끝을 따로 확인할 필요는 없었다.

문자열이 )로 시작한다면 첫 순회에서 바로 count가 -1이 되기 때문에 false가 반환된다.

문자열이 (로 끝난다면 모든 순회가 끝났을 때 count가 0이 아니므로 false가 반환된다.

즉, 아래 두 조건만으로 충분하다.

1. 순회 도중 count < 0이 되면 false
2. 순회가 끝났을 때 count === 0이면 true

---

정리

핵심 로직은 다음과 같다.

• (를 만나면 count + 1
• )를 만나면 count - 1
• 중간에 count가 음수가 되면 올바르지 않음
• 마지막에 count가 0이면 올바른 괄호

다음날 다시 풀어본 코드

function solution(s){
    // score이 음수가 되면 false 얼리 리턴
    score = 0
    
    for (const char of s) {
        if (char == "("){
            score += 1
        }
        else { // s 는 문제에서 무조건 "(" or ")" 이라 제시됨
            score -= 1
            
            if (score  < 0) {
                return false
            }
        }
    }
    
    // 다 돌고나서 score가 0이 되어야 함
    return score == 0
    
}