[프로그래머스 Level.2] 조이스틱 (탐욕법(Greedy)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 탐욕법(Greedy) > 조이스틱

 

 

 

문제 설명

 

 

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

 

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

 

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

 

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

 

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

 

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

 

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

 

 

 

 

 

나의 코드

class Solution {
    // 좌우 이동 방법은 총 세가지
    // 1. 오른쪽으로만 쭉 가는 경우
    // 2. 오른쪽으로 갔다가 왼쪽으로 가는 경우
    // 3. 왼쪽으로 갔다가 오른쪽으로 가는 경우
    public int solution(String name) {
        int answer = 0;
        int move = name.length() - 1; // 오른쪽으로만 쭉 가는 경우
        
        for(int i=0; i<name.length(); i++) {
            if(name.charAt(i) >= 'A' && name.charAt(i) <= 'N') {
                answer += (name.charAt(i) - 'A');
            } else {
                answer += ('Z' - name.charAt(i) + 1);
            }
            
            int idx = i+1;
            while(idx < name.length() && name.charAt(idx) == 'A') {
                idx++;
            }
            
            move = Math.min(move, i * 2 + (name.length() - idx)); // 오른쪽으로 갔다가 왼쪽으로 가는 경우
            move = Math.min(move, (name.length() - idx) * 2 + i); // 왼쪽으로 갔다가 오른쪽으로 가는 경우
        }
        
        answer += move;
        
        return answer;
    }
}

 

풀이

1. 각 위치마다 알파벳을 변경할 때 필요한 횟수를 카운팅 하고 좌우로 가장 짧게 이동하는 최소값을 구해 더해주면 된다.
2. 알파벳은 총 26개이고 'A'에서부터 시작하므로 'N'(14번 째)과 'O'(15번 째)를 보면 A에서 시작하여 조이스틱을 위로 올려 N은 13번 올려야하고 O는 14번 올려야 한다. A에서 시작하여 조이스틱을 아래로 내리면 N은 13번 내려야하고 O는 12번 내려야 한다. 따라서 N까지는 조이스틱을 위로(위로 하든 아래로 하든 같아서 내리는데 포함해도 상관 없음) O까지는 조이스틱을 아래로 내리는 것이 빠르다.
3. 그리고 좌우로 이동하는 것을 따져야 하는데 좌우로 이동하는 방법은 총 세가지 경우가 있다.
   (1) 처음부터 쭉 오른쪽으로 가는 경우
   (2) 오른쪽으로 갔다가 왼쪽으로 가는 경우
   (3) 왼쪽으로 갔다가 오른쪽으로 가는 경우
4. 이렇게 세 가지가 있으니 우선 answer를 오른쪽으로 전부 이동했을 경우로 두고 매 턴마다 해당 위치까지 갔다가 반대대쪽으로 쭉 가는 경우를 따져서 최소값을 구하면 된다.
5. name 크기만큼 for문을 돌면서 charAt()을 이용하여 'A' ~ 'N' 까지는 chatAt(i) - 'A' 만큼,  'O' ~ 'Z' 까지는 'Z' - charAt(i) + 1 을 만큼이 조이스틱을 위아래로 이동한 최소값이므로 answer에 더한다.
6. 그리고 중간에 'A'가 있는 경우에 오른쪽으로 갔다가 다시 왼쪽으로 가는 방법과 왼쪽으로 갔다가 다시 오른쪽으로 가는 방법이 최소값이 되는 경우가 생기는 것이므로 우선 int형 변수 idx를 생성해서 현재 인덱스에서 'A'가 아닌 다음 인덱스를 구한다.
7. 이렇게 구한 다음 인덱스 idx를 이용하여 좌우로 이동한 최소값을 구하기 위해 처음에 오른쪽으로 쭉 가는 경우인 name.lengh() - 1로 초기화 되어있는 answer와 해당 i 위치까지 오른쪽으로 갔다가 idx로 왼쪽으로 쭉 가는 경우와 idx까지 왼쪽으로 갔다가 i까지 오른쪽으로 가는 경우를 비교하여 최소값을 업데이트 한다.
8. 그리고 answer에 더해주면 좌우로 최소 이동 경우 + 각 자리마다 알파벳 변환 최소 조작 횟수를 모두 카운팅 하게 되는 것이므로 answer를 반환하면 된다.