[프로그래머스] 조이스틱 with JS

알고리즘 스프린트 7일차 - [프로그래머스] Lv 2. 조이스틱

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

프로그래머스

소요시간

1시간 10분

 

계획

풀이

• 이름의 각 알파벳을 A에서의 거리로 치환한다
  • 유니코드 값을 이용한 계산을 활용한다
• 좌,우 양방향으로 A가 아닌 곳을 탐색한다
  • 이름의 길이가 20을 넘지 않았기에 재귀로 탐색 가능할 것이라 판단했다.
  • DFS를 활용하여 탐색하였다
  • A가 아닌 지점을 모두 탐색하였을 때를 기저조건으로 정한다
    • 기저조건에 해당할 때 최솟값을 갱신한다

결과

코드

var answer = 1000000000;
var nameToNum = [];
function solution(name) {
    var alpha = [0];
    for (let i = 1; i < 14; i++){
        alpha.push(i);
    }
    for (let i = 12; i >= 1; i--){
        alpha.push(i);
    }
    
    let count = 0;    
    for(let i = 0; i < name.length; i++){
        nameToNum.push(alpha[name[i].charCodeAt(0) - 65]);
        if(name[i] != "A"){
            count++;
        }
    }
    
    let check = [];
    for(let i = 0; i < nameToNum.length; i++){
        check.push(false);
    }
    let sum = 0;
    let tempCount = 0;
    
    if(nameToNum[0] != 0){
        sum += nameToNum[0];
        tempCount++;
        check[0] = true;
    }
    findNext(0, check.slice(), sum, tempCount, count);
    
    return answer;
}

function findNext(idx, check, sum, count, maxCount){
    if (count == maxCount){
        answer = answer > sum ? sum : answer;
        return;
    }
    let left = idx;
    let right = idx;
    let tempCount = 0;
    for(let i = 1; i < check.length/2+1; i++){
        tempCount++;
        left -= 1;
        if(left < 0){
            left = check.length-1;
        }
        right += 1;
        if(right >= check.length){
            right = 0;
        }
        if(!check[left] && nameToNum[left] != 0){
            check[left] = true;
            findNext(left, check.slice(), sum+(nameToNum[left]+tempCount), count+1, maxCount)
            check[left] = false;
        }
        if(!check[right] && nameToNum[right] != 0){
            check[right] = true;
            findNext(right, check.slice(), sum+(nameToNum[right]+tempCount), count+1, maxCount)
            check[right] = false;
        }        
    }
}

마치며

평소 DFS에 굉장히 약해서 이번 문제를 보고 DFS를 잘 활용할 수 있을까 걱정했다.. 문제 유형이 DFS를 무조건 사용할 필요는 없었지만 DFS를 활용해서 풀 수 있을 것 같아서 시도해보았고 성공했다.

 중간에 디버깅을 하면서 종료조건과 방문한 지점에 대한 처리를 더 연습해야 겠다고 느꼈다. 앞으로도 DFS 더 많이 풀어보자!