[프로그래머스] (Java) 조이스틱 (그리디)

📑 1. 문제설명

---

💡 2. 접근방식

 

조이스틱을 양 옆으로 이동하는 좌우 이동 횟수(move) 

조이스틱 좌우로 이동하면서 알파벳 변경를 위해 상하 이동 하는 횟수(answer)

 

두 개를 answer에 누적하면서 더해줘야 한다.

 

여기서 문제되는 것은 단방향이 아니아 양쪽(좌,우)로 조이스틱이 움직일 수 있기 때문에 가장 빠른 경로를 찾아야 한다는 것이다. 이 때 연속된 AAA의 개수를 계산 해 주어야 한다. 

 

✅ 알파벳 변경

 

현재 인덱스에서 A를 빼준 값  vs Z부터 시작해서 현재 인덱스를 빼준 값 + 1

두 개를 비교해서 더 작은 값을 선택해 준다.

전자는 스틱을 정방향▼ A부터 순차적으로 Z로 내려가면서 바꾸는 거고

후자는 스틱을 먼저 역방향▲으로 1칸 돌려서 Z를 만든 다음에 반대로 해당 알파벳을 찾아가는 것이다. 

 

✅ 연속된 A갯수 확인 

 

⚡`index = i+1`

 

현재 위치 다음 문자부터 확인하려고 설정

현재 위치(i)는 이미 처리 중이기 때문에, 그 다음 위치(i + 1)부터 연속된 'A'를 찾기 위해 탐색을 시작 하는 것

 

while문은 연속된 'A'의 끝을 찾는 조건문이다.
인덱스가 길이보다 작고 현재 문자가 A인 경우에는 index++을 해서 다음 문자도 A인지 확인해준다.

 

⚡`index < length`

문자열의 끝에 도달하기 전까지 계속 탐색하는 것. 만약 탐색 중 문자열의 길이를 넘어서버리면 에러가 발생할 수 있기 때문에 이 조건을 붙여 준다.

 

⚡ `name.charAt(index) == 'A'`

현재 탐색 중인 문자가 'A'일 때만 index를 증가시키며 탐색 계속하고 'A'가 아닌 문자를 만나면 while문 종료

 for (int i = 0; i < name.length(); i++) {
     answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
     
     index = i + 1;
     while (index < length && name.charAt(index) == 'A') {
        index++;
 }

 

 

---

⭐ 3. 정답코드         

class Solution {
    public int solution(String name) {
        int answer = 0;
        int length = name.length();
        int index = 0; 
        int move = length-1; // 좌우 움직임 수(기본적으로 문자 길이-1)
        
        // 알파벳 변경 횟수(상하 움직임)
        for (int i = 0; i < name.length(); i++) {
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
       
        // 연속된 A 개수 확인
            index = i + 1;
            while (index < length && name.charAt(index) == 'A') {
                index++;
        }
        
        // 최소 이동 횟수(좌우 움직임)
        // 순서대로 가는 것과, 뒤로 돌아가는 것 중 이동수가 적은 것을 선택
        // 대신 BBAAAZ같은 경우 오른쪽으로 갔다가 왼쪽으로 가야 해서 이런 수식이 나옴
        // 여기서 index는 연속된 A의 마지막 위치
        move = Math.min(move, i * 2 + length - index);
        
        // BBBBAAAAAAAB 와 같이, 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우 고려
        move = Math.min(move, (length - index) * 2 + i);
        }
        
        // 문자 변경 횟수(answer)와 최소 이동 횟수(move)의 합
        return answer + move ;
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int[] diff={0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1};
        for(char c:name.toCharArray())
            answer+=diff[c-'A'];

        int length=name.length();
        int min=length-1;

        for(int i=0;i<length;i++){
            int next=i+1;
            while(next<length && name.charAt(next)=='A'){
                next++;
            }                
            min=Math.min(min,i+length-next+Math.min(i,length-next));
        }

        return answer+min;
    }
}

---

🐦 4. 같은 유형 문제(그리디)

 

[프로그래머스] (Java) 체육복 (Greedy)