[프로그래머스 JavaScript] 조이스틱

🚩 프로그래머스 Level2 조이스틱 -> 탐욕법(Greedy)

 

📖 문제 설명

두번째 그림과 같이 오락실 게임에서 이름 등록 과정을 생각하면 이해하기 좋습니다.

위아래 방향키는 알파벳 순서를 의미하고, 왼쪽오른쪽 방향키는 문자의 위치를 의미합니다.

주어진 문자열을 만들기 위해서는 최소한 몇번의 조작으로 만들수 있는지 구하면 됩니다.

즉, 왼쪽 오른쪽 방향키 횟수 + 위쪽 오른쪽 방향키 횟수 입니다.

 

👉 소스 코드  ⏰시간복잡도 O(n^2)

function solution(name) {
    var answer = 0;
    //좌우 이동 값
    //최대로 많이 움직이는 경우는 길이만큼 이동이므로 길이값만큼 설정
    let min = name.length - 1;
    
    for(let i=0; i<name.length; i++){

        //아스키코드값 변환
        let tmp = name.charCodeAt(i);
        
        //78(N) 보다 작을 경우 그냥 카운트해준다.
        if(tmp < 78){
           answer += tmp%65;
        }
        //78보다 클경우 이전 알파벳이 더 빠르다.
        else{
            answer += 91-tmp;
        }
        
        //좌우 이동 인덱스
        let nextIndex = i+1;
        
        while(nextIndex < name.length && name.charCodeAt(nextIndex) === 65)
            nextIndex += 1;
        
        //BBBAAAAAABA인 경우는 다시 왼쪽으로 돌아가는 것이 더 빠르다.
        //처음 위치로 돌아간 횟수(i*2) + 문자열길이 - A가 연속으로 나오는 지점의 다음값
        min = Math.min(min, (i*2) + name.length - nextIndex);
        
    }
    answer += min;
    return answer;
}

 

👨‍💻 코드 설명

반복문을 수행하면서 문자 한개씩 아스키 코드값으로 변환해줍니다.

그래서 78(N) 보다 작은 알파벳이면 그냥 위쪽 방향으로 옮겨주면서 만들어줍니다.

78(N) 보다 클 경우는 아래쪽 방향으로 거꾸로 옮겨주는게 더 빠르므로 Z의 다음값 91을 뺀값으로 설정합니다.

위의 과정을 반복적으로 거치면 알파벳 설정은 끝이 납니다.

 

이제 왼쪽, 오른쪽 커서의 방향을 설정해야합니다.

기본적으로 왼쪽에서부터 오른쪽으로 차례로 커서를 이동한다면 이동의 값은 문자열의 길이가 됩니다.

하지만 여기서 예외가 있습니다.

BBBAAAAAAABA 문자열이 있을때 오른쪽 부터 차례로 이동한다면 문자열의 길이인 12가 됩니다.

하지만 BBBAAAAAAABA 세번째 B를 작성하고 난 후, A가 연속해서 쭉 있습니다.

이럴때는 왼쪽으로 돌아가서 BBBAAAAAAABA 마지막 B를 작성하는게 훨씬 빠릅니다.

이때는 횟수가 세번째 B까지 오고 다시 처음으로 되돌아가므로 6 + 문자열길이 - B의 위치 1 = 7입니다.

따라서 이 예외를 while문으로 index의 위치를 구하고 그렇게 계산된 결과를 

Math.min 함수를 통해 문자열길이, 되돌아가는 횟수 중 작은 값을 선택해서 마지막 answer값에 더해주면 됩니다.

-저도 이 경우를 생각하지 못해 다른 사람의 풀이를 참고했습니다.