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

짝지어 제거하기(level 2)

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

---

풀이

stack을 이용하여 쉽게 풀 수 있었다. 다음의 단계를 거쳐 stack에 남아있는 알파벳이 있다면 0, 없다면 1을 리턴하도록 하였다.

 

입력한 문자열을 0부터 순회하면서

1. stack이 비어있다면 push한다.
2. stack이 비어있지 않다면 stack.pop()으로 가장위에 있는 값을 꺼낸다.
3. top과 현재 순회중인 알파벳의 값이 같다면 
   1. stack의 길이가 1보다 크다면 current의 값에 stack.pop()을 한번 더 한 값을 넣고 다시 반복한다.
   2. stack의 길이가 1보다 작다면 비교할 수 있는 대상이 없기 때문에 반복문을 종료한다.
4. top과 현재 순회중이 알파벳의 값이 같지 않다면
   1. top과 current 모두 push한다.
   2. 반복문을 종료한다. 

/*
input이 1,000,000이므로 O(nlogn)으로 끝내야 한다.

*/
function solution(s)
{
    let stack = [];
    for(let i=0;i<s.length;i++){
        let current = s[i];
        let notMatched = false;
        if(stack.length){
            while(!notMatched){
                let top = stack.pop();
                if(top === current){
                    if(stack.length>1){
                        current = stack.pop();   
                    }else{
                        notMatched = true;
                        break;
                    }
                }else{
                    stack.push(top);
                    stack.push(current);
                    notMatched = true;
                    break;
                }
            }
        }else{
            stack.push(current)
        }
    }
    
    return stack.length===0 ? 1 : 0;
}

 

 

더 나은 로직 또는 클린 코드를 위한 피드백은 감사히 받겠습니다.