[Programmers Level 2] 괄호 회전하기 Javascript

⚡문제정보

스택의 대표적인 문제 중 하나인 괄호 문자열 문제에 조건을 살짝 더 추가한 문제라고 할 수 있을 것 같습니다.

회전시키면 되는 문제인데 s의 길이만큼 다 회전을 시켜봐서

올바른 괄호가 되는 케이스의 숫자를 리턴하면 되는 문제입니다.

 

괄호를 구현하는건 쉬우니까 문자열을 회전시키는것만 유의하면 되겠네요

저는 회전 시킬 때 문자열의 substring 메서드를 이용했습니다. 

---

🔍접근방법

 

substr을 이용해 문자열을 회전시켜준다.

회전된 문자열들이 올바른 괄호인지 스택으로 확인해본다.

---

🔍나의 풀이

 

function solution(s) {
    let answer = 0
    for(i=0 ; i<s.length; i++) {
        let turn =  s.substring(i,s.length) + s.substring(0,i)
        let stack = []
        if(turn[0] == '}'|| turn[0] == ')' || turn[0] == ']' ) continue
        
        for(j=0; j<turn.length; j++) {
            if(turn[j] == '('|| turn[j] == '[' || turn[j] == '{' ) {
                stack.push(turn[j])
            }
            if(turn[j] == ')' && stack[stack.length-1] == '(' ) {
                stack.pop()
            }
            if(turn[j] == ']' && stack[stack.length-1] == '[' ) {
                stack.pop()
            }
            if(turn[j] == '}' && stack[stack.length-1] == '{' ) {
                stack.pop()
            }
            
        }
        if(!stack.length) answer += 1
    }
    return answer
}

 

코드 설명은 다음과 같습니다.

function solution(s) {
    let answer = 0
    // 정답을 넣어줄 answer 변수
    
    for(i=0 ; i<s.length; i++) {
        let turn =  s.substring(i,s.length) + s.substring(0,i)
        //문자열을 회전 시켜줘야하니까 substring메서드를 이용
        let stack = []
        //스택을 위한 배열 i가 증가할때마다 초기화
        if(turn[0] == '}'|| turn[0] == ')' || turn[0] == ']' ) continue
        //시작부터 닫힌괄호면 어차피 못하니까 넘어가기
        
        for(j=0; j<turn.length; j++) {
            if(turn[j] == '('|| turn[j] == '[' || turn[j] == '{' ) {
                stack.push(turn[j])
            }
            if(turn[j] == ')' && stack[stack.length-1] == '(' ) {
                stack.pop()
            }
            if(turn[j] == ']' && stack[stack.length-1] == '[' ) {
                stack.pop()
            }
            if(turn[j] == '}' && stack[stack.length-1] == '{' ) {
                stack.pop()
            }
            
        }
        // 괄호 알고리즘
        
        if(!stack.length) answer += 1
        //만약 스택이 비었다면 answer에 1더해줌
    }
    return answer
}

 

문제점 메모리도 많이 잡아먹고 런타임 시간도 너무 긴 알고리즘이 되어버렸습니다.

다른 사람 풀이보니 저보다 훨씬 빠른 속도로 문제를 푼 사람이 있어서 그 사람의 풀이를 참고해서

개선해봤습니다.

저랑 로직 자체는 비슷한데 안되는 케이스들을 빠르게 판단하고 break하는게

메모리 효율에서 큰 비중을 차지하네요

 

---

🔍다른사람의 풀이

function solution(s) {
    if(s.length % 2 === 1) return 0;

    let answer = 0;
    const mapping = { "}" : "{", "]" : "[", ")" : "("};

    for(let i = 0; i < s.length; i++) {
        const stack = [];
        const rotate = s.slice(i) + s.slice(0, i);
        let flag = true;

        for(let j = 0; j < s.length; j++) {
            if(rotate[j] === "[" || rotate[j] === "(" || rotate[j] === "{" )
                stack.push(rotate[j]);
            else {
                const last = stack.pop();
                if(last !== mapping[rotate[j]]) {
                    flag = false
                    break;
                }
            }
        }

        if(flag) answer++;
    }

    return answer;
}

객체를 통해 한번이라도 괄호가 성립하지 않으면 더이상 연산을 하지않고

break하는 방법이네요 이 방법이 핵심인 것 같습니다.

---

🔍좀 더 개선한 풀이

function solution(s) {
    if(s.length % 2 === 1) return 0;
    let answer = 0
    let obj = { "}" : "{" , "]" : "[" , ")" : "("}
    for(i=0 ; i<s.length; i++) {
        let turn =  s.substring(i,s.length) + s.substring(0,i)
        let stack = []
        let flag = true
        if(turn[0] == '}'|| turn[0] == ')' || turn[0] == ']') continue

        for(j=0; j<turn.length; j++) {
            if(turn[j] == '('|| turn[j] == '[' || turn[j] == '{' ) {
                stack.push(turn[j])
            }
            else {
                const pop = stack.pop();
                if(pop != obj[turn[j]]) {
                    flag = false
                    break;
                }
            }
        }

        if(flag) answer++;
    }
    return answer
}

편안한 런타임이 되었네요