[CodeKata] isValid 함수 구현하기

문제

 

isValid는 여러 괄호들로 이루어진 String 인자를 받는다. 인자가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 (, ), [, ], {, }으로 6개 있다. 한 번 괄호를 시작했으면, 같은 괄호로 끝나야 하며 괄호 순서가 맞아야 한다.

 

() → true

()[]{} → true

(] → false

([)] → false

{[]} → true

 

---

풀이

function isValid(s) {
	if(s.length % 2) {
    	return false;
    } // 홀수는 무조건 false
    
    const bracket = {
    	"(": ")",
        "{": "}",
        "[": "]"
    }
    const ref = [];
    
    for(let i=0; i<s.length; i++) {
    	if(bracket[s[i]]) {
        	ref.push(s[i]);
        } else if(bracket[ref.pop()] !== s[i]) {
        	return false;
        }
    }
    return true;
}

연달아서 나오는 (){} 괄호는 접근할 수 있었으나, {()}와 같이 감싸고 있는 괄호 풀이를 접근하지 못해 구글링을 했다. 찾아보니 스택 구조로 풀이해야 한다고 했다.

 

여는 괄호는 계속해서 ref에 추가하고(닫는 괄호를 만날 때까지), 여는 괄호가 아니라면 최근 ref에 추가된 값과 비교하여 맞지 않으면 false를 반환하도록 되어 있다. 

 

{}[]라면 {를 ref에 추가하고, 다음 }닫는 괄호를 만나서, ref에 들어가 있는 {값을 pop하여 값이 같은지 확인하고, 다음 []를 계속해서 앞과 같이 비교하고 true를 반환하게 된다.

 

{[]}라면 여는 괄호{[를 이어서 ref에 추가하고, ]닫는 괄호를 만나서 기존 ref에 있는 {[값중 마지막 인덱스 값 [을 pop하여 비교하고, 이어서 }닫는 괄호를 만나서 ref에 남아있는 {과 비교해서 true를 반환한다. 

 

 

신기했던 동료 풀이

function isValid(s) {
	while(s.includes("()") || s.includes("[]") || s.includes("{}")) {
    	s = s.replace("()", "");
        s = s.replace("[]", "");
        s = s.replace("{}", "");
    }
    retrun s === '' ? true : false;
}

while문을 이용해서 (){}[]이 남지 않을 때까지 없애고, 비어 있는 문자열이 되면 true, 조금이라도 남아 있다면 false를 반환한다.