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

문제 링크

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

풀이 과정

그리디 문제입니다. 아래 그림을 보며 설명하겠습니다.

위 예시의 초기 값 x 에서 110 은 한 번 등장합니다. 110 을 이동시키기 위해 한 쪽으로 치워논다고 가정하면, 두 번째 줄에서 볼 수 있듯, 사라진 110 으로 인해 새로운 110이 등장하게 됩니다. 따라서, x가 100111100인 경우엔 110은 총 두 번 등장하고, 남겨진 문자열은 100이 됩니다.

문자열을 사전순으로 정렬한 위 그림을 보면, 110 은 111을 제외한 다른 문자열들보다 뒤에 위치해야한다는 것을 알 수 있습니다. 즉, 여기선 문자열 110은 문자열 111보다 앞선다는 것을 확인할 수 있습니다.

문자열 110이 111보다 앞선다는 사실 하나만으로, 모든 경우에서 사전순으로 앞서는 절대적인 위치를 알 순 없습니다. 그래서 위와 같이 여러 경우에 110을 삽입한 문자열이 사전순으로 맨 앞에 위치하는 경우를 직접 구해보면서 규칙을 찾을 수 있었습니다.

110을 제거한 나머지 문자열을 remain 이라고 했을 때, 7개의 remain 문자열 각각에 문자열 110을 삽입해, 사전순으로 가장 앞에 오는 문자열은 위 그림과 같습니다. 따라서, 다음과 같은 규칙을 발견할 수 있었습니다.

• remain이 0으로 끝나는 경우, 무조건 remain 뒤에 110을 위치시켜야 사전 순으로 가장 앞섭니다.
• remain이 1로 끝나는 경우, 연속된 1이 끝나는 지점 앞에 110을 위치시켜야 사전 순으로 가장 앞섭니다.

코드

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

    for (let i = 0; i < s.length; i++) {
        let x = s[i];
        let stack = [];
        let cnt = 0;

        for (let j = 0; j < x.length; j++) {
            if (stack.length < 2) stack.push(x[j]);
            else {
                if (x[j] === "0") {
                    if (stack[stack.length - 1] === "1" && stack[stack.length - 2] === "1") {
                        stack.pop();
                        stack.pop();
                        cnt++;
                    } else stack.push(x[j]);
                } else {
                    stack.push(x[j]);
                }
            }
        }

        let target = stack.length;

        for (let i = stack.length - 1; i >= 0; i--) {
            if (stack[i] === "1") {
                target = i;
                continue;
            }

            break;
        }

        let res = "";
        for (let i = 0; i < target; i++) res += stack[i];
        while (cnt--) res += "110";
        for (let i = target; i < stack.length; i++) res += stack[i];

        answer.push(res);
    }

    return answer;
}

console.log(solution(["1110", "100111100", "0111111010"]));
console.log(solution(["1011110", "01110", "101101111010"]));