[programmers/js] 110 옮기기

110 옮기기

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

문제 설명

주어진 문자열에서 "110" 패턴을 모두 제거한 후, 다시 문자열에 삽입하여 사전 순으로 가장 앞선 문자열을 만드는 문제입니다.

문자열 배열 s가 주어지고, 각 문자열에 대해 해당 연산을 수행한 결과 중 사전 순으로 가장 빠은 문자열 배열을 반환합니다.

풀이

핵심 아이디어는 "110"을 전부 제거한 뒤, '0' 바로 뒤에 몰아서 붙이면 가장 사전 순으로 빠른 문자열이 된다는 점입니다.

최종 코드

function solution(s) {
    // 110을 0 바로 뒤에 추가
    const answer = [];
    
    for (const str of s) {
        const st = [];
        let cnt = 0;
        for (const c of str) {
            st.push(c);
            
            if (st.length >= 3) {
              	// 1. 문자열을 스택에 하나씩 넣고, 최근 3개의 문자가 "110"이면 제거하며 개수를 센다.
                const last3 = st.slice(-3).join("");
                if (last3 === "110") {
                    st.pop();
                    st.pop();
                    st.pop();
                    cnt += 1;
                }
            }
        }
        
        let insertIndex = 0;
        for (let i = st.length - 1; i >= 0; i--) {
            if (st[i] === "0") {
                insertIndex = i + 1;
                break;
            }
        }
        
        // 2. 제거하고 남은 문자열에서 마지막 '0' 위치를 기준으로 "110"을 삽입한다.
        const result = [...st.slice(0, insertIndex), ...Array(cnt).fill("110"), ...st.slice(insertIndex)].join("");
        answer.push(result);        
    }
    
    return answer;
}