[프로그래머스] level.2 조이스틱 ★

 

프로그래머스

---

나의 풀이 

 

상당히 어려웠다. 

커서 왼쪽이동이 없으면 쉬운데 왼쪽이동 때문에 생각해야될 부분이 많다. 

 

나는 두 부분으로 나누었다. 

1. 알파벳을 수정하는 위 or 아래 조작의 최소값을 각 문자마다 구한다. 

2. 알파벳을 수정하기위해 현재 커서 위치를 이동 해야하는데 이때 왼쪽 or 오른쪽 조작의 최단경로를 구한다.  

 

1번 + 2번을 하면 답이나온다 .

 

1.  name에서 각 문자별로 최소한의 조이스틱 조작

 

 

const getCharMin = () => {
        const first = 65;
        const last = 90 + 1; // 커서를 아래로 이동 시켜야하기때문에  + 1
        
        return [...name].reduce((acc, cur) => {
            return acc += Math.min(cur.charCodeAt(0) - first, last - cur.charCodeAt(0))},0)
    }

아스키 코드를 활용해서  다음 알파벳으로 조작할 때와 이전 알파벳을으로 조작할 때를 모두 구한뒤 Math.min을 통해 최소 값을 구해준다. 

단, 이전 알파벳으로 조작할 때는 기본값이 A부터시작하기 때문에 첫 문자가 Z가 아니라서  + 1 을 해줘야 Z부터 시작이된다. 

 

이렇게 각각의 문자마다 조이스틱 최소 조작을 구한뒤 전부 더해준다. 

뭐 reduce를 사용해도되고 따로 변수를 선언해서 for문이든 forEach문을 사용해도 상관없다.  (문자 길이가 20 이하이기 때문에) 

 

 

 

2. 커서 위치 이동 최단 경로 

 

이 부분이 어려웠다. 

오른쪽으로 쭉 갈때가 최단경로일 때가 있고 

오른쪽으로 갔다가 되돌아와서 첫 부분에서 name 끝부분으로 이동해서 진행하는 경우가 최단 경로일 때도 있다. 

아니면 아예 name 뒷 부분부터 시작해서 앞쪽으로 다시 넘어오는 경우가 최단경로일 때도 있다. 

 

이걸 코드로 잘 표현해줘야한다. 

 

let move = name.length - 1;

for(let i = 0; i<name.length; i++) {
        let index = i + 1; // 다음 값들을 확인할때 사용
        let length = name.length
            
        //연속된 A 개수 확인
        while(index < length && name.charAt(index) === "A"){
            index++;
        }
        move = Math.min(move, i*2 + length - index, (length - index) * 2 + i);
    }

 

먼저 Math.min 안에 있는 코드를 예제를 통해서 이해해보자 

만약 nmae = "BBABAAABB" 이라면?

 

 

1) move 

왼쪽에서 오른쪽으로 계속 이동하는 조작 횟수이다. 

 

 

2) i * 2 + length - index

왼쪽에서 오른쪽으로가 가다가  다시 왼쪽을 통해서 반대편으로 이동하는 조작 횟수이다. 

 

 

 

3) (length - index) * 2 + i 

처음부터 뒤쪽에서 부터 시작해서 다시 앞쪽으로 이동하는 조작 횟수이다. 

 

 

이 3개중에서 최소값이 move가 된다. 

 

지금 이 예제에서의 최소 조작은 아래와 같다. 

 

 

아래 표는 for문이 진행됨에 따라 변화하는 수치들이다. 

 

i * 2 + length - index 를 보면

i = 0 일때 B를 조작하고 바로 뒤로 이동 쭉이동한뒤 다시 앞으로 이동한다. 

i =  1 일때 두 번째 B까지 조작하고 뒤로 계속 진행한다. 

i = 2 일때 세 번째에 있는 A까지 간뒤에 뒤로 계속 진행한다. 

i = 3 일때 네 번째에 있는 B까지 이동하고 뒤로 계속 진행한다. 

이 이후는 쭉 낭비되는 조작이다. 

 

 

 

 

전체 코드 

function solution(name) {
    let move = name.length - 1;
    
    const getCharMin = () => {
        const first = 65;
        const last = 90 + 1; // 커서를 아래로 이동 시켜야하기때문에  + 1
        
        return [...name].reduce((acc, cur) => {
            return acc += Math.min(cur.charCodeAt(0) - first, last - cur.charCodeAt(0))},0)
    } 
    
    for(let i = 0; i<name.length; i++) {
        let index = i + 1; // 다음 값들을 확인할때 사용
        let length = name.length
            
        //연속된 A 개수 확인
        while(index < length && name.charAt(index) === "A"){
            index++;
        }
        move = Math.min(move, i*2 + length - index, (length - index) * 2 + i);
    }

    return getCharMin() + move;
}

 

 

 

 

 

---

 

 

 

참고

 

https://bellog.tistory.com/152