[프로그래머스] 고득점 키트 - 그리디2

오늘 푼 문제

 

2. 조이스틱 / Lv.2 / 시간 : 89분(타임오버)

programmers.co.kr/learn/courses/30/lessons/42860?language=javascript

코딩테스트 연습 - 조이스틱

function solution(name) {
    var answer = 0;
    let len = name.length;
    let pos = 0;
    let code = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    name = name.split('');
    
    while(!name.every(s=>s==='A')){
        for(let i=0; i<len; i++){
            if(name[pos+i]!==undefined && name[pos+i]!=='A'){ //right
                pos = pos+i;
                answer+=i;
                break;
            }else if(name[pos-i<0?len+pos-i:pos-i]!=='A'){ //left
                pos = pos-i<0?len+pos-i:pos-i;
                answer+=i;
                break;
            }
        }

        let upDown = code.indexOf(name[pos]);
        name[pos] = 'A'
        upDown = upDown>13?26-upDown:upDown;
        answer+=upDown;
    }
    
    return answer;
}

 

키포인트

1. 알파벳을 변경하는 부분보다 위치 이동에 신경써야 함. 알파벳 변경은 항상 A에서 시작하기 때문에 이전의 선택이 아무런 영향을 주지도 않음. N보다 큰 알파벳의 경우 커서를 아래로 이동하는 것만 신경쓰면 됨.

2. 이동의 경우 매번 현재 위치에서 오른쪽이나 왼쪽 중 A가 아닌 알파벳이 더 가까이 있는 곳으로 이동하는 걸 선택하면 됨. 그리디가 아니라 DFS 라는 의견이 보이는데 문제 설명이 헷갈리게 적혀 있어 그렇지 풀이 자체는 그리디가 맞다. 최종적인 조작 횟수의 최소화는 신경쓰지 말고 당장 최선의 선택만 하게 풀자.

 

 

헤맸던 부분 

1. 오른쪽으로 가는 경우나 왼쪽으로 가는 경우 모두 길이가 같을 때 오른쪽을 우선으로 가야함. (설명 진짜 개 날림으로ㅅㅂ 개빡침)

2. 커서가 처음 위치에서 왼쪽이나 아래쪽으로 overflow는 가능하지만, 마지막 위치에서 오른쪽이나 위쪽으로 overflow는 불허함.