[프로그래머스] 올바른 괄호

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

티스토리 에디터에서 코드박스를 보면 행간이 괜찮은데 글을 다 작성하고 나서 볼 때는 너무 다닥다닥 붙어있어서 가독성이 나쁘다. 며칠간 카카오 오류로 티스토리를 볼 수 없어서 벨로그 글들을 많이 찾아봤는데 가독성이 좋아서 옮길까 고민했다...

 

문제

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

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

 

제한 사항

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

입출력 예

"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

접근 과정

안풀려서 잠깐 접어두고 있었다. 그리고 다른 못풀었던 문제 중에도 스택으로 푸는게 있었다. 그래서 그날 스택에 대한 강의를 들었고 그다음날 강아지랑 놀다가 갑자기 번뜩 아이디어가 떠올랐다. 이것도 스택이겠거니 했는데 구체적으로 푸는 법은 생각이 안났다. 그래서 일단 반복문 돌렸다 (...)

 

1. ) 로 시작하거나 ( 로 끝나는 경우, 홀수인 경우는 짝을 지을 수 없으니 바로 리턴할 것

2. 저 조건이 모두 없는 경우 ( 와 )의 갯수를 세고 개수가 같을 경우 true를 리턴

 

//실패한 초기 코드
function solution(s) {
        if (s[0] === ")" || s[s.length - 1] === "(" || s.length % 2 === 1)
          return false;

        let obj = {
          "(": 0,
          ")": 0,
        };

        for (let char of s) {
          if (char === "(") obj["("]++;
          else obj[")"]++;

        }
        return obj["("] === obj[")"] ? true : false;
      }

 

다행히도 가장 문제의 효율성 검사는 통과한다. 하지만 걸리는 부분이 있어 통과하지 못했다.

 

())(()

이런 케이스가 있다. ( 와 ) 의 개수가 동일하지만 짝이 맞지 않는 유일한 케이스다.

내 코드는 반복문 순회가 모두 끝난 다음 개수를 세는데 그렇기 때문에 중간에 짝이 발생하지 않는 과정은 캐치하지 못한다. 반복문 내에서 계속 짝이 맞는지 개수를 확인해야 한다.

( 보다 )의 개수가 더 많은 시점에서 바로 끊어주면 된다. 

 

(가 더 많은 경우

(( 이렇게 늘어나고 있는 경우는 뒤에 )가 짝을 맞춰 닫아줄 가능성이 생긴다. 만약 모두 닫아주지 못한다면(= 개수가 다르다면) 그 때 false를 뱉으면 된다.

 

)가 더 많은 경우

하지만 ()) 이런 경우에서는 무슨 짓을 하더라도 짝을 맞춰줄 수 없다. 바로 false를 뱉는다.

 

해결 코드

  function solution(s) {
        if (s[0] === ")" || s[s.length - 1] === "(" || s.length % 2 === 1)
          return false;

        let obj = {
          "(": 0,
          ")": 0,
        };

        for (let char of s) {
          if (char === "(") obj["("]++;
          else obj[")"]++;

          if (obj["("] < obj[")"]) return false;
        }
        return obj["("] === obj[")"] ? true : false;
      }

 

다 풀고 제출할 때 실수로 마지막줄 return문에 === 를 >= 로 써서 냈는데 바로 효율성 검사에 걸리더라

최대한 낭비를 줄여야 한다 🙃

 

보완 사항

굳이 객체까지 만들 필요가 없다. count 변수 만들어주고 +1 -1 하는 방법도 있음. 그때는 마지막 카운트가 0이면 true가 된다