[JS] 110옮기기

 

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

프로그래머스

처음에 문제 풀이방식을 너무 어렵게 생각해서 헤맨 문제였다.

 

규칙자체는 간단하다.

 

1. 문자열 중 "110" 이 들어간 부분을 모두 빼주고 그 개수를 세준다.

2. 남은 문자열중 "11" 이 처음 나오면 11 전에 110 * cnt 만큼의 문자열을 삽입해준다.

3. "11"이 없다면 마지막으로 나온 0의 다음에 110*cnt만큼의 문자열을 삽입해준다.

4. 그외 경우는 "1"만 있는 경우이므로 110*cnt + "1" 을 반환해준다.

 

 

110을 한번 삽입한다면 무조건 110을 반복하게 해야 사전순으로 더 빠르다. 그 이유는 아래와 같다.

 

만약 11로 시작하는 부분이 나온다면  그앞에 하나의 0이라도 넣는게 이득이기에 모든 110을 넣어야 한다. 하지만 "11"이 없다면 110이 가장 안좋은 케이스이므로 마지막으로 나온 0의 다음에 110을 넣어줘야한다.

 

 

 

위처럼 문제접근 자체는 잘했는데 이전 문제에 링크드 리스트를 활용한 시간복잡도 문제가 있었어서.. 링크드 리스트로 풀다가 뭔가 꼬여버려서 시간이 오래걸린 문제였다. (그냥 내장함수 썼더니 금방 풀었다.. 시간자체도 차이 안날듯 하다)

 

 

 

핵심은 110을 어떻게 빼주냐인데, 괄호 문제처럼 스택을 활용하면 이를 좀더 쉽게 해결할 수 있었다.

 

 

function solution(s) {
    
  
    return s.map(str => {
        
        const [newStr , cnt ] = find110(str)
        const idx11 = newStr.indexOf("11")
        if(idx11!==-1) return newStr.slice(0,idx11)+"110".repeat(cnt)+newStr.slice(idx11)
        const zeroIdx = newStr.lastIndexOf("0")
        if(zeroIdx!==-1) return newStr.slice(0,zeroIdx+1)+"110".repeat(cnt)+newStr.slice(zeroIdx+1)
        return "110".repeat(cnt) + newStr
        
    })
    
}

const find110 = (str) => {
    const stk = []
    let cnt = 0
    for(const c of str){
        stk.push(c)
        while(stk.length>2 && stk[stk.length-1]==="0" && stk[stk.length-2]==="1" && stk[stk.length-3]==="1"){
            stk.pop()
            stk.pop()
            stk.pop()
            cnt +=1
        }
    }
    
    return [stk.join(""),cnt]
}