개발일지/TIL

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

JangKroed 2023. 4. 20. 01:11
728x90
반응형

문제 설명

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

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

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

 

제한사항

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

 

입출력 예

s answer
"()()" true
"(())()" true
")()(" false
"(()(" false

 

728x90

풀이 - 1

열린 소괄호와 닫힌소괄호의 갯수를 카운트할 변수를 각각 숫자타입으로 초기화 한 뒤 반복문을 통해 문자열 처음값이 열린 소괄호일때 인덱스가 0이면 열린 소괄호 카운트하고 반복문 다음 순서로 넘기고 이전인덱스값에 따라 조건문을 통해 풀어보려고 했다.

function solution(s){
    // 카운트 숫자변수 초기화 - 1
    let firstCount = 0;
    // 카운트 숫자변수 초기화 - 2
    let secondCount = 0;
    // 반복문
    for (let i = 0; i < s.length; i++) {
        // if - 문자열 첫번째 인덱스가 열린 소괄호일때
        if (s[0] === "(") {
            // if - 인덱스 값이 0일경우 1번 카운트값++, continue
            if (i === 0) {
                firstCount++;
                continue;
            }
            // if - 이전 인덱스 값이 같으면서 열린소괄호 일때 1번 카운트값++
            if (s[i] === s[i - 1] && s[i] === "(") firstCount++;
            // else if - 인덱스 값이 다르고 열린괄호 시작일 경우 1번과 2번 카운트가 같은지 비교, 다르면 return false;
            else if (s[i] !== s[i - 1] && s[i] === "(" && firstCount !== secondCount) return false; 
            // else if - 2번 카운트값++;
            else secondCount++;
        } else return false;
    }
    return true;
}

테스트 케이스는 모두 통과하였고 시간복잡도는 O(n)으로 작성되었으나 정확성 테스트와 효율성테스트를 각각 반타작정도하여 실패하게 되었다.

 

정확성 테스트만 생각해보았을때, 이전 코드에서 조건문사용이 잘못된 느낌이 들었고 가독성도 떨어지는것 같아 수정하여 다시 풀어보았다.

 

반응형

풀이 - 2

풀이 1에서 우선적으로 예외처리할 사항을 처리하고 그다음 로직을 짜보았다.

function solution(s){
    if (s[0] !== "(") return false;
    
    let openCount = 1;
    let closeCount = 0;
    for (let i = 1; i < s.length; i++) {
        // 각 소괄호의 갯수를 세고 같지않으면 return false;
        if (s[i] === "(") {
            const isStringExist = s[i] === s[i - 1];
            const isCountExist = openCount === closeCount;
            if (!isStringExist && !isCountExist) return false;
            else if (!isStringExist && isCountExist) {
                openCount = 0;
                closeCount = 0;
            }
            openCount++;
        }
        else closeCount++;
    }
    return true;
}

가독성이 좀더 나..아졌나? 싶기도 하고 여전히 정확성과 효율성 테스트를 통과하지 못했다.. 그나마 점수만 조금 올랐다 정도 ?

 

 

풀이 - 3

도저히 다른 풀이가 생각나지 않아 요즘 대세라는 ChatGPT의 도움을 받아보았다.

function isBalanced(string) {
  const stack = [];
  for (let char of string) {
    if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      if (!stack.length) {
        return false;
      }
      stack.pop();
    }
  }
  return !stack.length;
}

처음엔 변수배열을 초기화하여 선언한 뒤 열린 소괄호일때 배열에 push하고 닫힌 소괄호일때 pop하는 방식을 진행하고 이때 pop 메서드 사용 이전에 빈배열이면 false를 리턴하는식으로 진행되는 코드를 알려주었는데 공간복잡도상 불리하고 효율성테스트를 통과하지못해 최적화 하는 방법으로 변경해달라고 하였다.

 

function solution(s) {
    // count 변수를 0으로 초기화
    let count = 0;
    // 문자열의 각 문자에 대해 반복
    for (let char of s) {
        // 문자가 여는 괄호인 경우 count 증가
        if (char === '(') count++;
        // 문자가 닫는 괄호인 경우 count 감소
        else if (char === ')') count--;
        // count가 음수인 경우 false 반환
        if (count < 0) return false; 
    }
    // count가 0인 경우 true를 return
    return count === 0; 
}

어찌보면 first, seconed로 나누던 open, close로 count를 나누어 쓰지않고 위 코드 처럼 count를 더하거나 빼주는 방식을 생각하지못해 아쉬웠던것 같다. 생각보다 간단한걸 앞으로 알고리즘 열심히 해야겠다..

 

참고로 풀이 3번의 두가지 코드는 O(n)에서 O(1)로의 공간 복잡도를 줄이고 배열에서 요소를 푸시하고 팝할 필요를 제거하여 시간 복잡도도 줄이게 되었다. - ChatGPT 설명

 

다른풀이

다른사람 풀이를 참고하여 좀 더 코드 가독성이 좋고 연산자가 줄어 시간복잡도상 간소하게 이점을 볼수있는 코드를 구현해보았다.

function solution(s){
    let count = 0
    for (let char  of s) {
        count += char  === '('? 1: -1
        if(count < 0) return false
    }
    return count === 0;
}

삼항연산자 적극활용해야겠다.. (물론 코드 가독성을 크게 해치지 않는 선에서)

728x90
반응형