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

문제 요약

• 문자열에서 모든 "110"을 뽑아 임의 위치에 다시 넣어 사전순으로 가장 앞서는 문자열을 만든다.
• 여러 문자열에 대해 각각 최적 변형 결과를 반환한다.

처음 무한 루프가 난 이유

• "110"을 찾자마자 항상 맨 앞에 붙이는 단순 이동은 문자열을 바꾸지 않는 경우가 있어 상태가 정체된다.
• 예: "1110" → index=0 → 앞에 "110"을 다시 붙이면 그대로 "1110" → 다음 반복에도 동일 동작 → 무한 루프.

최적 접근: 스택으로 모두 제거 → 한 번에 삽입

• 스택으로 문자열을 선형 탐색하며 "110"이 나오면 제거하고 개수를 센다.
• 남은 문자열에서 “마지막 0” 뒤가 “110”들을 몰아서 넣었을 때 사전순이 가장 작다. 마지막 0이 없다면 맨 앞에 삽입.
• 이유: 남은 문자열의 0들 앞에 1을 밀어넣으면 사전순이 커지므로, 가장 오른쪽의 0 뒤에만 붙이는 게 최적.

알고리즘

• 스택에 문자를 push하며 직전 3글자가 1,1,0이면 pop 3회하고 카운트+1.
• 남은 문자열에서 뒤에서부터 첫 0의 다음 위치를 삽입 지점으로 정한다(없으면 0).
• 그 위치에 "110"을 count만큼 연속 삽입.
• 시간복잡도 O(N), 공간 O(N). 배열/스택 한 번만 순회.

JavaScript 코드 (Programmers 포맷)

function solution(strings) {
    const results = new Array(strings.length);
    for (let i = 0; i < strings.length; i++) {
        results[i] = transformToLexicographicallySmallest(strings[i]);
    }
    return results;
}

function transformToLexicographicallySmallest(s) {
    const stack = [];
    let count110 = 0;

    for (let i = 0; i < s.length; i++) {
        stack.push(s[i]);
        const len = stack.length;
        if (len >= 3 && stack[len - 3] === '1' && stack[len - 2] === '1' && stack[len - 1] === '0') {
            stack.pop(); stack.pop(); stack.pop();
            count110++;
        }
    }

    const remain = stack.join('');
    let insertIdx = -1;
    for (let i = remain.length - 1; i >= 0; i--) {
        if (remain[i] === '0') { insertIdx = i + 1; break; }
    }
    if (insertIdx === -1) insertIdx = 0;

    const prefix = remain.substring(0, insertIdx);
    const suffix = remain.substring(insertIdx);

    let mid = '';
    for (let i = 0; i < count110; i++) mid += '110';

    return prefix + mid + suffix;
}

간단 팁: 빈 문자열, "0"이 하나도 없는 경우(모두 '1')는 맨 앞 삽입이 정답이다. 스택 제거는 선형이라 대용량에서도 시간초과 없이 안정적이다.