[프로그래머스] 짝지어 제거하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/12973?language=javascript 

코딩테스트 연습 - 짝지어 제거하기

 

- s의 길이는 최대 1,000,000이다. 즉 O(NlogN) 이하로 처리해야 한다.

- 문자열 문제에서 이정도의 길이제한이 주어진다면, 이중 for문 이상의 알고리즘을 구현하지 못하므로 스택/큐를 고민해야한다.

 

function solution(s)
{
    let stack = []
    for(let char of s){
        if(stack.length === 0 ) stack.push(char)
        else{
            if(stack[stack.length-1] === char){
                stack.pop()
            }
            else {
                stack.push(char)
            }
        }
    }
    let answer = stack.length === 0 ? 1 : 0
    return answer
}

 

- node.js는 따로 stack을 위한 빌트인 객체는 존재하지 않고, 그냥 빈 배열을 이용해서 스택을 활용하면 된다. 가장 기본적인 연산인 push와 pop도 array 메서드에 그대로 잘 구현되어 있으니 말이다.

 

- 스택이 비어있다면, 일단 스택에 넣는다. 비어있지 않다면, 스택의 top과 해당 문자를 비교해서 같다면 스택에서 하나를 제거하고, 아니면 해당 문자도 스택에 push한다.

 

- 모든 문자를 한 번씩 순회하고, 스택이 비어있다면 올바르게 짝짓기를 완료한 것이므로 1을 return, 비어있지 않다면 짝짓기에 실패했으므로 0을 return하면 된다. 매우 쉬운 문제!