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

짝지어 제거하기

❓ 문제설명

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

 

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

b aa baa > bb aa > aa > 

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

🚫 제한조건

문자열의 길이 : 1,000,000이하의 자연수

문자열은 모두 소문자로 이루어져 있습니다.

✔ 입출력 예

s	result
baabaa	1
cdcd	0

💡 풀이

function solution(s) {
  const stack = []

  // 최초 shift를 활용한 queue 형식으로 구현하였는데 시간초과
  // 이 후 index를 통해 순회하는 방식으로 진행
  for (let i = 0; i < s.length; i ++) {
    const c = s.charAt(i)

    if(stack[stack.length - 1] === c) {
      stack.pop()
    } else {
      stack.push(c)
    }
  }

  return stack.length > 0 ? 0 : 1
}

📝 해설

문자열을 처음부터 읽으면서 직전 스택과 비교해서 같으면 pop, 다르면 현재 문자를 stack에 push하여 전체 문자열을 반복한 후 stack에 남은 문자가 있는지 확인하는 방식으로 해결.

 

스택과 큐를 사용하여 푸는 문제인데 배열에 shift 메서드를 사용하여 문자열을 배열로 split하여 queue 방식으로 문제를 풀었을 때 시간초과 이슈가 발생하여 문자열을 순회하였다. 앞으로도 queue를 사용해야할 때 대상 데이터가 문자열일 경우 index를 통해 순회하는 방식을 사용해야할 것 같다.

📚 참고자료

- Javascript 스택/큐 (추가예정)