[프로그래머스-42860] 조이스틱

[그리디]-조이스틱

프로그래머스

 

문제 설명

조이스틱(4가지 방향)으로 알파벳 이름 완성할 때 조작 횟수의 최솟값 구하기

 

[조이스틱 방향]

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

 

 

[입출력 예제]

name	return
"JEROEN"	56
"JAN"	23

 

해당 문제를 이해하는데 어려움이 있었다. 맨 처음에 A 알파벳 딱 하나만 존재한다고 이해했다. 그래서 JAN의 경우 J를 만들기 위해 9번 스틱을 위로 움직여야 하는 것은 이해가 됐지만, 그 다음 A를 만들기 위한 조작을 왜 안하는지 이해가 되지 않았다..

여러 블로그 내용들의 도움을 받아 문제를 해결했다!

 

우선, 맨 처음에 A 알파벳 하나만 존재하는 것이 아니라 name의 길이만큼 A가 채워진거였다..! 즉, JAN은 세글자니까 AAA 이렇게 초기화가 되어있다!

 

그리고 조이스틱을 반드시 움직여야 하는 횟수는 크게 2가지로 나뉜다!

1. 알파벳 찾기 → 조이스틱 ▲/▼ 로 'A' -> 특정 문자열 변경

2. 위치 이동하기 → 조이스틱 ▶︎/◀︎ 로 커서 위치 변경하기

 

여기서, 각 최솟값을 찾는 방법은 다음과 같다.

1. 알파벳 찾기 → 조이스틱 ▲/▼ 로 'A' -> 특정 문자열로 변경

1-1) 'A' -> 특정 문자열 변경 (▲ 방향으로 바꾸기)

1-2) 'A' -> 'Z'로 만들기 -> 특정 문자열로 변경 (▼ 방향으로 바꾸기)

즉, JAN의 경우 A -> J으로 바꿀 때 알파벳 찾는 방법은

1-1) 'A' -> 'J' : 총 ▲ 스틱 9번 움직이기

1-2) 'A' -> 'Z' -> 'J' : 총 17번 움직이기

 

2. 위치 이동하기 → 조이스틱 ▶︎/◀︎ 로 커서 위치 변경하기

2-1) 0번 인덱스부터 N번 인덱스까지 이동 → N-1

2-2) 0번 인덱스부터 오른쪽으로 이동하다가 'A'를 만나면 다시 왼쪽으로 이동하기 → index*2 + (len-next)

2-3) 맨 뒤부터 왼쪽으로 이동하다가 'A'를 만나면 다시 오른쪽으로 이동하기 → (len-next)*2 + index

 

ex) JAN의 경우

 

코드

function solution(name) {
    let updown = 0;
    const len = name.length;
    let move = len-1; // 2-1
    
    for(let i=0; i<len; i++) {
        // 1. ▲/▼ 로 알파벳 바꾸는 조작
        // - A부터 바꾸는 방법 or Z로 이동(▼) 후 해당 알파벳으로 바꾸는 방법
        updown += Math.min(name[i].charCodeAt(0)-65, 90-name[i].charCodeAt(0)+1);
        
        // 2. ◀/▶ 로 커서 옮기는 조작
        // 2-1) 0번째 인덱스부터 마지막 인덱스까지 순차로 옮기는 방법
        // 2-2) 오른쪽으로 이동하다가, A만나면 뒤로 가는 방법
        // 2-3) 뒤부터 시작하다가, A만나면 앞으로 가는 방법
        let next = i+1;
        while(next < len && name[next] === 'A') {
            next++; // 연속된 A개수
        }
        const right = (i*2) + len-next;
        const reverse = (len-next)*2 + i;
        move = Math.min(move, right, reverse);
    }
    
    return updown + move;
}

---

참고 사이트

https://html-jc.tistory.com/650

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