Today I Learned

코로나 증상이 완화되어서 출근을 했다. 오늘부터는 dfs/bfs와 더불어 그리디 문제들을 병행해서 풀어볼 예정이다.

조이스틱(Greedy)

• 문제
  오락실에서 게임이 끝나면 상하좌우 조이스틱으로 자신의 이름을 알파벳 대문자로 새긴다. 이때 조이스틱을 가장 적게 움직이면서 이름을 적는 방법을 찾아라.

• 구현 방법

1. 알파벳이 아스키코드로 char 에 저장된다는 점을 이용했다. 해당 알파벳과 A의 차이, Z와 해당 알파벳의 차이+1 이 두가지 케이스 중 더 적은횟수의 케이스를 답에 더한다.

2. 사실 알파벳 변환은 쉬웠지만 이동이 문제였다. 그냥 순차적으로 가면 편하겠지만 중간에 A가 연속으로 있을경우 뒤로 돌아서 맨 뒤부터 순회하면서 하는 경우가 더 횟수가 적게 나올 수 있기 때문에 이 부분을 보정해야했다.

3. 이동 횟수는 int m에다 할당했다. 기본 이동횟수는 그냥 계속 오른쪽으로 간다는 가정 하에 l-1. 연속되는 A의 개수를 구하기 위해 while문으로 A가 어디까지 연속으로 있나 체크한다.

4. i2+l-index : 앞으로 갔다가 뒤로 돌아가는 경우의 횟수. i까지 왔다가 되돌아가서(i2) 다시 순회하고(l) A연속으로 된 부분은 뺀다(-index).

5. (l-index)2+i : 처음부터 뒤로 가는 경우의 횟수. 전체에서 연속된 A의 마지막인덱스를 빼면 A가 아닌 남은 뒷자리의 갯수가 나오고(l-index) 그걸 왔다 갔다(2)하고 다시 A연속 이전까지 순회(i).

6. 위의 두 경우와 그냥 순차로 갔을 경우(m)의 최솟값을 이동횟수로 답에 더해주면 끝.

• 최종 코드

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        char[] ch = name.toCharArray();
        int l = name.length();
        int m = l-1;
        
        for(int i=0; i< l; i++){
            int index = i+1;
            while(index<l && ch[index] == 'A'){
                index++;
            }
            m = Math.min(m, i*2+l-index);
            m = Math.min(m, (l-index)*2 +i);
            
            int numA = (int) ch[i] - (int)'A';
            int numZ = (int) 'Z' - (int) ch[i] + 1;
            answer += Math.min(numA, numZ);
        }
        answer += m;
        
        return answer;
    }
}