[프로그래머스] 110 옮기기

문제

110 옮기기

https://school.programmers.co.kr/learn/courses/30/lessons/77886

 

 

풀이

설명

변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 구하는 문제입니다.

 

먼저 문자열 내에 존재하는 모든 110을 없애고, 카운트를 증가시킵니다.

110을 제거하고 남은 문자열에 대해서도 같은 작업을 반복합니다.

 

문자열을 넣을 위치를 정해야 합니다.

우선순위는 다음과 같습니다.

1. 111 바로 앞
2. 마지막 0 바로 뒤
3. 첫 번째

마지막으로 110을 카운트만큼 반복한 문자열을 해당 위치에 넣어서 만든 문자열을 반환하면 됩니다.

 

예시 코드

function solution(s) {
  return s.map(processBinaryString);
}

function processBinaryString(binaryString) {
  const targetPattern = "110";
  const stack = [];
  let targetPatternCount = 0;

  for (const char of binaryString) {
    stack.push(char);

    if (stack.length >= 3 && stack.slice(-3).join("") === targetPattern) {
      targetPatternCount++;
      stack.pop();
      stack.pop();
      stack.pop();
    }
  }

  const modifiedString = stack.join("");
  if (targetPatternCount === 0) return modifiedString;

  const targetPatternString = targetPattern.repeat(targetPatternCount);
  const indexOf111 = modifiedString.indexOf("111");
  const indexOfLastZero = modifiedString.lastIndexOf("0");

  if (indexOf111 !== -1)
    return (
      modifiedString.slice(0, indexOf111) +
      targetPatternString +
      modifiedString.slice(indexOf111)
    );
  else if (indexOfLastZero !== -1)
    return (
      modifiedString.slice(0, indexOfLastZero + 1) +
      targetPatternString +
      modifiedString.slice(indexOfLastZero + 1)
    );
  else return targetPatternString + modifiedString;
}

 

문자열을 수정할 때 정규식을 사용할 경우, 시간 초과가 발생할 수 있어 스택을 사용했습니다.