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

https://programmers.co.kr/learn/courses/30/lessons/12973

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

 

 

1. 문제 설명

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

예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

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

---

2. 코딩 시작

• 같은 알파벳 2개라는 단어에 꼳혀 연속된 단어를 제거하려고 시도
• 연속된 단어를 찾기 위해 정규식 시도
  • 소문자로 이루어진 연속된 2개를 공백으로 치환 : str.replace(/([a-z)\1/,"");
• 정확성은 통과했으나 효율성에서 시간 초과 발생

function solution(s)
{
    //시간초과
    s = s.replace(/([a-z])\1/,'');

    while(s !== s.replace(/([a-z])\1/,'')) {
        s = s.replace(/([a-z])\1/,'');
    }

    return !s.length ? 1 : 0;
}

---

3. 답안

• 스택을 이용
  • 스택에 있는 값과 비교할 대상이 같은 경우 스택에서 제거. 다를 경우 스택에 추가
  • 한번의 루프로 해결

function solution(s)
{
    const stack = [];

    for(let i = 0, len = s.length; i < len; i++) {
        if(!stack.length || stack[stack.length - 1] !== s[i]) {
            stack.push(s[i]);
        } else {
            stack.pop();
        }
    }

    return !stack.length ? 1 : 0;
}

---

4. 결론

• 루프가 반복적으로 처음부터 다시 실행이 되어야 할 때, 스택을 고려해보자.