[코딩테스트] 스택/큐 괄호 맞추기

스택에 대해 공부할 때, 스택 관련 문제 예시로 나왔던 괄호 맞추기 문제가 프로그래머스에 있어서 풀어보았다!

기존에 풀이 방식을 한 번 봤음에도 불구하고, 막상 코딩 테스트 형식으로 접하니 엄청 쉽게 풀리진 않았다.

덕분에 내가 놓치고 있었던 스택의 작동 방식과 예외 케이스 처리의 중요성을 확실히 체감할 수 있었다!

 

처음 풀어봤던 코드

function solution(s){
    var answer = true;
    var arr = [];
    s = s.split("");
    
    for(i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            arr.push(s[i]);
        } else arr.pop();   
    }
    
    if (arr.length === 0) {
        return answer = true;
    } else return answer = false;
    
    return answer;
}

 

채점 결과

정확성: 61.8
효율성: 30.5
합계: 92.3 / 100.0

 

처음에는 단순히 여는 괄호는 스택에 넣고, 나머지는 꺼내는 방식으로만 처리했다.

근데, 닫힌 괄호가 먼저 오는 경우에 대한 예외 처리가 없어서, 스택이 비어있는 상태에서 pop()을 하게 되면 의도치 않게 undefined를 꺼내는 상황이 생겼고.... 이 이유로 일부 케이스를 통과하지 못하는 문제가 발생했다 😫!!

 

수정된 코드  (메모리 & 시간 & 문제 링크와 같은 자세한 정보는 해당 링크를 통해 확인해 주세요! )

function solution(s){
    var answer = true;
    var arr = []; // 스택 추가
    s = s.split(""); // 문장 자르기

    for(i = 0; i < s.length; i++) {
        if (s[i] === "(") { // 열린 괄호일 경우 스택에 추가
            arr.push(s[i]);
        } 
        else if (s[0] === ")") {
            return answer = false; // 첫 번째 요소가 닫힌 괄호일 경우 answer = false
        } 
        else arr.pop(); // 그렇지 않을 경우 제거
    }

    if (arr.length === 0) {
        return answer = true;
    } else return answer = false;

    return answer;
}

 

첫 번째 요소가 닫는 괄호인 경우 즉시 false를 반환하도록 조건을 추가하니 테스트 케이스에 모두 통과가 출력됐다!

 

다른 분들이 푼 코드

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

 

이 코드는 스택을 직접 사용하지 않고, 열리는 괄호일 때는 +1, 닫히는 괄호일 때는 -1을 연산하는 방식을 사용하셨다!

괄호가 열리기 전에 닫히는 경우 (cum < 0)를 중간에 바로 체크해서 빠르게 반복문을 나갈 수 있도록 만드셨는데,

내가 작성한 코드에 비해 훨씬 간결하고 직관적인 로직이라 많이 배웠다!

 

이 외에도

 var result = s.match(/(\(|\))/g);

 

이런 식으로 match 함수를 이용한 분들도 있었는데

해당 표현식은 아직 익숙하지 않은 방식이라 한 번 제대로 공부하고 넘어가야겠다고 생각했다.

괄호처럼 특정 패턴을 추출하거나 분석할 때 match, replace, test 같은 문자열 관련 메서드를 잘 활용하면 더 다양한 풀이가 가능하 ㄹ것 같다!!