[PGS] 짝지어 제거하기 - Level 2

📚 문제 내용

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

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

baabaa → bbaa → aa →

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

제한사항

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

입출력 예

s	result
baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #2

문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

✍️ 문제 분석

처음에 생각한 풀이

1. 문자열을 순회하면서 stack에 하나씩 넣는다.
2. stack의 top에 있는 원소와 현재 문자가 같으면 pop
3. stack의 top에 있는 원소와 현재 문자가 다르면 push
4. 문자열이 끝날 때까지 진행하고, 최종 stack의 크기가 0이면 1을 반환하고 1 이상이면 0을 반환

최종 풀이

처음에 생각한 풀이와 동일

💻 내 코드

function solution(s)
{
    const strArr = s.split('');
    const stack = [];
    
    strArr.forEach(el => {
        if(stack.length > 0 && stack[stack.length - 1] == el)
            stack.pop();
        else
            stack.push(el);
    })
    
    if(stack.length == 0) return 1;
    
    return 0;
}

• 문자열 s의 각 글자를 담은 배열 생성
• 비어 있는 stack을 하나 생성
• 문자열 배열을 돌면서, stack의 길이가 0보다 크고, top에 있는 문자와 현재 문자가 같은 경우에만 pop()을 하고, 그 외의 경우엔 push()
• 문자열 배열 순회가 끝난 뒤, stack 길이가 0이면 1을 리턴하고, 그 외의 경우에는 0을 리턴

📌 다른 풀이

const solution = (s) => {
  if (s.length % 2 != 0) return 0;
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    const b = s.charAt(i);
    if (stack[stack.length - 1] === b) {
      stack.pop();
    } else {
      stack.push(b);
    }
  }

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

• 2개씩 짝지어서 제외시키는 거니까 길이가 홀수인 경우에는 바로 0을 반환해주는 코드
• 연산을 최대한 줄이는 방향을 생각해 보자...

✨ 새롭게 알게 된 점

바로 이전 문자와 비교해야 하는 케이스가 있으면 Stack을 활용해 보자!

🙇‍♂️ 참고 자료

[Javascript] 배열(문자열)에서 연속되는 원소 지우기