[JS] 110 옮기기

🔒 문제 (프로그래머스 월간 코드 챌린지 시즌 2)

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

 

🌊 입출력

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

---

 

🔑 해결

🌌 알고리즘

110을 어떻게 배치해야 사전순으로 가장 앞설 수 있는지 그 방법을 찾는 것이 핵심인 문제.

0과 1을 이용한 3자리 문자열 조합을 살펴보면 110이 앞설 수 있는 조합은 111 뿐이다.

=> 원래 문자열보다 사전순으로 앞설 수 있는 경우는 연속된 1 앞에 110을 삽입하는 경우

따라서 할 일은 다음과 같다.

1. 문자열을 변형하며 나오는 모든 110 탐색하여 제외시킨 문자열 얻기
2. 얻은 문자열에서 1이 연속된 부분의 시작 지점 찾기
3. 1이 연속된 부분의 시작에 탐색한 110 모두 붙여 답 찾기

이 때 s의 길이가 크기 때문에 1번 과정은 stack을 이용한다.

function solution(s) {
    const answer = [];
    
    for(const x of s) {
        const stack = [];
        let cnt = 0;
        
        // 변형 과정 중 나오는 '110' 모두 제외한 문자를 가진 stack 생성
        for(let i = 0; i < x.length; i++) { 
            const third = x[i];
            
            if(stack.length > 1) {
                const second = stack.pop();
                const first = stack.pop();
                if(first === '1' && second === '1' && third === '0') {
                    cnt++;
                    continue;
                } else {
                    stack.push(first, second, third);
                }
            } else {
                stack.push(third);
            }
        }
        
        // '110' 구성 불가 시 그 문자열 자체가 답
        if(!cnt) {
            answer.push(x);
        } else {     // 1이 연속되는 지점의 시작 찾기
            const arr = [];
            
            while(stack.length) {
                const last = stack.pop();
                if(last === '0') {
                    stack.push(last);
                    break;
                } else {
                    arr.push(last);
                }
            }
            
            const str = '011';  // 스택에 반대로 넣은 것 고려
            while(cnt) {    // 1의 연속이 시작되는 지점에 '110' 삽입
                arr.push(...str);
                cnt--;
            }
            
            arr.reverse();
            const result = stack.concat(arr).join('');
            answer.push(result);
        }
    }
    
    return answer;
}

 

 

 

 

참고 https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-110-%EC%98%AE%EA%B8%B0%EA%B8%B0-JS