[프로그래머스] 110 옮기기(javascript)

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

프로그래머스

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

---

입출력 예sresult

["1110","100111100","0111111010"]

---

풀이

stack을 이용하였습니다. 문자열에 0이 들어올때마다 앞에 11이 있는지 확인하며 있다면 제거합니다.

110은 111을 제외한 모든 숫자보다 큽니다. 즉, 0보다 무조건 뒤에 위치해야 합니다.

두번째 예제를 예로

첫 for문을 돌고나면 stack은 [1, 0, 0] str은 '110110'이 됩니다.

여기서 마지막 0의 index를 찾고 그뒤에 이어붙여주면 됩니다. 

전체 코드

function solution(s) {
  var answer = s.map((v) => {
    const stack = [];
    let str = "";
    for (const right of v) {
      if (stack.length > 1) {
        const mid = stack.pop();
        const left = stack.pop();
        `${left}${mid}${right}` === "110" ? (str += "110") : stack.push(left, mid, right);
      } else {
        stack.push(right);
      }
    }

    const baseStr = stack.join("");
    const zeroIdx = baseStr.lastIndexOf("0") + 1;
    return zeroIdx === -1
      ? str + baseStr
      : baseStr.slice(0, zeroIdx) + str + baseStr.slice(zeroIdx);
  });
  return answer;
}

solution(["1110", "100111100", "0111111010"]);