[프로그래머스/js] 괄호 회전하기 (Lv. 2)

문제

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

`프로그래머스 :: 괄호 회전하기 :: Lv. 2`

 

문제 리뷰

우리는 '괄호' 하면 가장 먼저 떠오르는 것이 있습니다.

Stack의 기본 예제로 나오는 착한 문제죠..

 

이번 문제에서도 역시, Stack을 이용하는 방식으로 풀이해 보았는데요,

하다 보니 이것 저것 해보고 싶어서 로직에 수정을 거쳤습니다.

 

첫 번째 시도 (정답) - if문 (Time: 231.19 ms, Memory: 38.2 MB)

code

function solution(s) {
    let answer = 0;
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        const sCopy = [...s];
        while (sCopy.length > 0) {
            const target = sCopy.shift();
            
            if (target === ']' && stack[stack.length - 1] === '[') {
                stack.pop();
            }
            else if (target === '}' && stack[stack.length - 1] === '{') {
                stack.pop();
            }
            else if (target === ')' && stack[stack.length - 1] === '(') {
                stack.pop();
            }
            else stack.push(target);
        }
        
        if (stack.length === 0) answer += 1;
        
        stack = []; // stack 초기화
        s = [...s.slice(1), s[0]].join(''); // 회전
    }
    
    return answer;
}

 

두 번째 시도 (정답) - js object (Time: 254.88 ms, Memory: 38.1 MB)

code

const match = {
    ']': '[',
    '}': '{',
    ')': '(',
}

function solution(s) {
    let answer = 0;
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        const sCopy = [...s];
        while (sCopy.length > 0) {
            const target = sCopy.shift();
            
            if (match[target] && match[target] === stack[stack.length - 1]) stack.pop();
            else stack.push(target);
        }
        
        if (stack.length === 0) answer += 1;
        
        stack = []; // stack 초기화
        s = [...s.slice(1), s[0]].join(''); // 회전
    }
    
    return answer;
}

 

세 번째 시도 (정답)

code

const match = {
    ']': '[',
    '}': '{',
    ')': '(',
}

function solution(s) {
    let answer = 0;
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        const sCopy = new Queue(s); // Queue 구현
        while (sCopy.size() > 0) {
            const target = sCopy.dequeue();
            
            if (match[target] && match[target] === stack[stack.length - 1]) stack.pop();
            else stack.push(target);
        }
        
        if (stack.length === 0) answer += 1;
        
        stack = []; // stack 초기화
        s = [...s.slice(1), s[0]].join(''); // 회전
    }
    
    return answer;
}

class Queue {
    constructor(str) {
        this.queue = [...str];
        this.head = 0;
        this.tail = str.length - 1;
    }
    
    enqueue(value) {
        this.queue.push(value);
        this.tail += 1;
    }
    
    dequeue() {
        const returnValue = this.queue[this.head];
        this.head += 1;
        
        return returnValue;
    }
    
    size() {
        return this.tail - this.head + 1;
    }
}

 

소감

첫 번째 시도 (정답)	두 번째 시도 (정답)	세 번째 시도 (정답)
if문 (Time: 231.19 ms, Memory: 38.2 MB)	js object (Time: 254.88 ms, Memory: 38.1 MB)	js object & Queue (Time: 91.10 ms, Memory: 37.4 MB)

 

shift() 사용을 지양하고자 Queue로 구현한 결과, 시간 측면에서 비용을 꽤나 절약한 모습을 확인할 수 있었습니다.

 

이미 풀이법이 널리 알려져 있는.. 익숙한 문제였지만,

왠지 이것저것 시도해보고 비교해보고 싶은 마음이었고

기록을 남겨보았습니다. ㅋ

 

잼있는 시간이었습니다.