12973. 짝지어 제거하기

프로그래머스 12973번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 스쿨

풀이

아이디어

어렵게 생각하지 말자… 적절한 비유인지 모르겠는데, 버블정렬마냥 짝을 계속 옮겨가면서 제거해야겠다고 생각하고 처음 접근했었다. 그래서 스택을 두개 써서 두 스택을 옮겨다니며 제거를 했었는데 시간초과가 났었다. (그럴만도 함 문자열 길이가 1,000,000인데 O(N²) 접근을 시도한 것…)

다시 생각해보니 문자열을 한번만 순회하면서, 자신의 앞 원소만 바라보며 당장 제거할 수 있다면 제거하고, 아니면 스택에 넣어서 뒤 원소한테 운명을 맡기는 방법으로 간단히 해결할 수 있었다.

코드

function solution(s) {
  const stack = [];
  for (const c of s) {
    if (stack.length === 0) {
      stack.push(c);
      continue;
    }
    const top = stack[stack.length - 1];
    if (c === top) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }

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