[프로그래머스/Level2] 조이스틱 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 그리디

1. 커서를 상하로 이동하며 알파벳을 변경할 수 있는 최솟값을 구한다.

answer += Math.min(ch - 'A', 'Z' - ch + 1);

 

 

2. 연속된 알파벳 'A'가 끝나는 지점을 찾는다.

int idx = i+1;            
while(idx < len && name.charAt(idx) == 'A') {
    idx++;
}

 

 

3. 좌우 이동 최소 횟수를 구한다.

- (i*2) + len - idx ⇒ 오른쪽으로 갔다가 왼쪽으로 움직여 바꾸고 시작점으로 돌아간 후, 왼쪽으로 움직여 마지막 위치로 이동해서 바꾸는 경우

   ㄴ (i*2) ⇒ 좌에서 우로 움직인 후, 다시 원점으로 돌아가는 횟수

 

- (len - next)*2 + i ⇒ 시작점에서 왼쪽으로 움직여 마지막 위치의 값을 바꾸고, 다시 오른쪽으로 움직여 시작점으로 돌아와 나머지를 바꾸는 것

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(String name) {
        int answer = 0; // 조이스틱 조작 횟수
        int len = name.length();
        int move = len-1;   // 기본 최소 좌우이동 횟수 (좌,우,커서)
                
        // 해당 커서 알파벳 변경 최솟값 (위,아래,커서)
        for(int i = 0 ; i < len ; i++) {
            char ch = name.charAt(i);
            answer += Math.min(ch - 'A', 'Z' - ch + 1);
            
            // 연속된 'A'가 끝나는 지점 찾기
            int idx = i+1;            
            while(idx < len && name.charAt(idx) == 'A') {
                idx++;
            }
            
            // 좌우이동 최소 횟수 구하기
            move = Math.min(move, i*2 + len - idx);     // 순서대로 가기
            move = Math.min(move, (len - idx)*2 + i);   // 뒤로 돌아가기
        }
        
        return answer + move;
    }
}

 

---

💦 어려웠던 점

- 좌우 인덱스 이동하는 부분의 구현이 헷갈렸다,,,

 

 

🧐 새로 알게 된 내용

- 좌우 인덱스 이동하는 부분 구현 방법,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Java/자바] 프로그래머스 Lv2 - 조이스틱 (Greedy/탐욕법)

[탐욕법(Greedy)] 조이스틱 - JAVA

 

- 가장 이해가 잘 되었던 설명은 이 글

[프로그래머스] 조이스틱 자바