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

문제 설명

주어진 문자열에서 "110"을 제거한 후 원하는 위치에 다시 삽입하여, 사전 순으로 가장 앞서는 문자열을 만들어야 합니다.

---

제한 사항

• 문자열 배열 s의 길이는 최대 1,000,000입니다.
• 각 문자열의 길이는 최대 1,000,000이며, 모든 원소의 길이 합이 1,000,000을 초과하지 않습니다.

---

해결 방법

알고리즘: 스택 활용, 문자열 조작

1. 문자열을 순회하며 "110"을 찾아 제거하고, 개수를 기록합니다.
2. 제거 후 남은 문자열에서 '0'이 등장하는 마지막 위치를 찾습니다.
3. 찾은 위치에 "110"을 모두 삽입하여 가장 작은 사전 순 문자열을 만듭니다.
4. 각 문자열을 처리한 후 결과를 반환합니다.

---

시간 복잡도

• 각 문자열을 한 번 순회하여 "110"을 제거하는 과정: O(N)
• 문자열을 다시 조합하는 과정: O(N)
• 전체 문자열 배열을 처리하는 경우: O(N)
• 최악의 경우 전체 길이 1,000,000에 대해 수행되므로 O(N)로 해결할 수 있습니다.

---

구현 코드

function solution(s) {
  let answer = [];

  for (const str of s) {
    const stack = [];
    let count110 = 0;

    for (const ch of str) {
      stack.push(ch);
      if (
        stack.length >= 3 &&
        stack[stack.length - 3] === "1" &&
        stack[stack.length - 2] === "1" &&
        stack[stack.length - 1] === "0"
      ) {
        stack.pop();
        stack.pop();
        stack.pop();
        count110++;
      }
    }

    const remaining = stack.join("");
    const lastZeroIndex = remaining.lastIndexOf("0");
    const insertion = "110".repeat(count110);

    let newStr;
    if (lastZeroIndex === -1) {
      newStr = insertion + remaining;
    } else {
      newStr =
        remaining.slice(0, lastZeroIndex + 1) + insertion + remaining.slice(lastZeroIndex + 1);
    }

    answer.push(newStr);
  }

  return answer;
}