programmers. 110 옮기기

문제

링크

코딩테스트 연습 - 110 옮기기

풀이

입력 받은 수열에서 110을 추출할 수 있을 만큼 추출한 후에 추출이 끝난 수열에 110이 들어갈 자리를 찾은 후에 끼워넣어 최종 수열을 만들면 되는 문제

사전순으로 앞에 오게끔 만들려면 0이 앞에 있어야한다

그렇기 때문에 추출이 끝난 문자열에서 제일 처음에 오는 11을 찾은 후에 그 앞에 추출한 110을 넣어주면 가장 앞에 오는 수열을 만들 수 있다

만약 11이 없다면 가장 마지막 0을 찾아서 그 뒤에 110을 넣어주면된다

시간 초과에 걸리지 않기위해 배열을 스택처럼 사용해서 풀었다

코드

    function findIdx(str) {
        return str.search('11')>=0 ? str.search('11') : (str.lastIndexOf('0')>=0) ? str.lastIndexOf('0')+1: -1;
    }

    function make110(cnt){
        let str = '';
        for(let i=0; i<cnt;i++){
            str +='110';
        }
        return str;
    }
    function is110(arr){
        return arr[arr.length-1]==='1'&&arr[arr.length-2]==='1'&&arr[arr.length-3]==='0';
    }

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

        answer = s.map(str=>{
            const arr = str.split('');
            let stack = [];
            let cnt = 0;
            console.group()
            while (arr.length){
                stack.push(arr.pop());

                if(is110(stack)){
                    for(let i=0; i<3;i++){
                        stack.pop();
                    }
                    cnt++;
                }
            }
            str = stack.reverse().join('');

            const index = findIdx(str);
            console.log(index)

            console.log(str)
            const tail = str.slice(index,str.length);
            str = str.slice(0,index)+make110(cnt)+tail;

            console.groupEnd()
            return str;
        })
        return answer;
    }

is110

현재 수열에서 뽑아낸 스택이 110이면 110을 빼버리고 cnt를 1 올리는 함수

이후 110들이 들어갈 자리에 cnt 수 만큼 반복해서 들어간다

make110

위에서 늘린 cnt 수만큼 110 수열을 만드는 함수

findIdx

110이 들어갈 인덱스를 찾는 함수