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

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

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

 

문제 풀어보기: https://school.programmers.co.kr/learn/courses/30/lessons/12973

 

풀이보기

function solution(s) {
    let str = s.split('');
    
    while(str.length > 0) {
        let findStr = false;
        if(str.length % 2 !== 0) return 0;
        
        for(let i = 0; i < str.length; i++) {
            if(str[i] === str[i + 1]) {
                str.splice(i, 2);
                findStr = true;
                break;
                }
            }
        if(!findStr) return 0;
        }
    
    return 1;
}

 처음에 작성한 코드이다. 테스트 케이스는 다 통과했지만 효율성 테스트는 통과하지 못했다.

아무래도 s의 길이가 최대 1,000,000이기 때문에 효율적인 코드가 필요한 것 같다.

단순히 처음부터 배열을 순회하며 현재 인덱스와 다음 인덱스가 같은지 확인하고 같다면 splice로 삭제하게끔 했다.

또한 문자열 길이가 홀수이거나 findStr 변수로 연속된 문자가 없을 경우 0을 리턴하도록 해줬다.

마지막에 while 문을 빠져나온다면 str 길이가 0일테니 1을 리턴해줬다.

 

아무래도 splice는 제거할 때마다 배열을 재구성하기 때문에 비효율적인 것 같다.

그래서 찾은 방법은 스택이다!

function solution(s) {
    let stack = [];
    
    for (let i = 0; i < s.length; i++) {
        if (stack.length > 0 && stack[stack.length - 1] === s[i]) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }

    return stack.length === 0 ? 1 : 0;
}

스택은 후입선출의 특징을 가지고 있으며 문자열의 요소를 하나씩 넣으며 비교할 수 있다.

따라서 먼저 스택이 비어있는지 확인하고, 현재 문자와 스택의 마지막 문자가 같은지 확인한다.

조건을 충족하면 짝지어있는 문자임으로 삭제해주고, 아니라면 스택에 push 해준다.

 

문제에서 알려준 예시인 baabaa로 적용해보면,

1. 스택에 b가 추가된다. => stack = ['b']

2. 그다음 a에 대하여, 들어있는 b와 a는 같지 않으므로 그대로 a가 스택에 추가된다. => stack = ['b', 'a']

3. a와 앞선 a는 같으므로 삭제해준다. => stack = ['b']

4. b와 앞선 b는 같으므로 삭제한다. => stack = []

5. 현재 스택은 비어있으므로 그냥 a가 추가된다. => stack = ['a']

6. 마지막으로 현재 a와 앞선 a가 같으므로 삭제된다. => stack = []

7. 스택이 비어있으므로 1이 리턴된다.

 

스택을 활용하면 더 효율적으로 문제를 해결할 수 있다.

2단계로 넘어오면서 더 다양하게 문제를 풀어야하겠구나 싶었다 ㅠ