[JS] 조이스틱

문제가 그리디 파트에 있어서 곰곰히 생각해봤는데 결국 이 문제는

 

알파벳을 돌리는 최소개수 + 조이스틱을 좌우로 돌리는 최소 개수를 구하는 문제였다.

 

알파벳을 돌려서 나오게 하는 최소개수는 사실 쉽다. N보다 작을때는 그냥, N보다 뒤에나오는 알파벳이 나오면 26에서 뺀 값을 주면 된다.

(이부분이 그리디인가?)

 

 

문제는 조이스틱을 좌우로 돌리는 최소를 찾는 부분이었다.

 

"BBBAAAAAAAB"

"BAAABAAAAAAAAAAAB"

 

위와같이 한쪽으로만 가지 않고 쭉 가거나, A가나와도 우선 진행한 후에 돌아와야하는 케이스들이 많았기 때문이다.

 

 

문제를 읽어보니 입력으로 주어지는 문자의 총 케이스가 20개라서 그냥 완전탐색을 활용해서 체크하면 되겠다 라는 생각이 들었다.

 

따라서 dfs방식으로 좌우를 계산해줬다.

 

 

 

위 방식으로 풀었는데 16,17케이스에서 자꾸 통과가 안되었다.

 

원인은 "AAAAAAAA"로 들어오는 경우가 있을 수 있는 것

 

해당 경우를 예외처리 해주었더니 통과되었다.

 

 

 

function solution(name) {
    
    if (!name.replaceAll('A',"").length) return 0
    
    const alphaToNum = (str) => {
        const n = str.charCodeAt()-65
        return n > 12 ? 26-n : n
    }
    let ret = 0
    
    for (const s of name){
        ret += alphaToNum(s)
    }
    
    const dfs = (arr,idx,step,dp) => {
        const tmpArr = [...arr]
        const tmpDp = [...dp]
        tmpArr[idx] = 'A'
        tmpDp[idx] += 1
        
        if (arr.every(v => v==='A')) return step -1
        if (tmpDp[idx] >2) return name.length-1
        
        const leftIdx = idx === 0 ? name.length-1 : idx-1
        const rightIdx = idx === name.length-1 ? 0 : idx+1
        
        const left = dfs(tmpArr,leftIdx,step+1,tmpDp)
        const right = dfs(tmpArr,rightIdx,step+1,tmpDp)
        
        return Math.min(left,right)
        
        }
    
    
    const arr = [...name]
    const dp = new Array(name.length).fill(0)
    
    return ret + dfs(arr,0,0,dp) 
}