[JAVA] Programmers <Greedy LV2> 조이스틱

일단 문제의 핵심은 조이스틷의 조작 횟수의 최솟값을 구하는 것이다.

즉, 만들어야할 문제가 어느 방향으로 움직여야 하는 지 정해야한다. 문제에서 문자는 모두 대문자로 주어진다고 했으니, 아마 아스키코드 값을 이용하여 판단하면 될 것이다.

출처: https://needjarvis.tistory.com/643

표에서 A ~ Z가 65 ~ 90이므로 78번인 N을 기준으로 N 뒤 문자들은 조이스틱을 아래로 조작하여 만들게 코드를 작성하면 풀 수 있다. 

...

라고 매번 처음에는 생각한다. 

 

그러나 여기서 반드시 생각하고 넘어가야 하는 아주 중요한 사항이 있다!

A일때는 조이스틱을 조작하지 않아도 문자가 이미 완성되어 있는 상태이다. 

즉, JAAAAAAAAAJ 라면 굳이 A들을 모두 거치고 가는 방법보다는 첫 문자를 입력 후 마지막 문자로 커서를 이동시켜 마지막 J를 입력하는 것이 조이스틱 사용의 최솟값이라는 것!! 사실상 이 로직을 구현하는 것이 문제의 핵심이라고 할 수 있다.

 

커서를 이동하는 최대값은 우직하게 오른쪽으로만 커서를 이동시키는 것이므로 배열의 길이 - 1이 된다. 

각 위치에서 다음 문자가 조이스틱을 조작해야하는 문자가 나올 때까지의 거리를 측정하여여

현재 인덱스 + 배열의 길이(가야할 거리) - A의 길이 -현재 인덱스(돌아갈 거리) 의 계산 값이 최대 이동 횟수보다 작은 최적의 해라면 그 값을 적용시켜 마지막에 커서 이동 횟수를 더해주면 된다.

---

package com.choonham;

class Solution {
	public int solution(String name) {
		int answer = 0;
		int[] strArray = new int[name.length()];
		for (int i = 0; i < name.length(); i++) {
			int temp = (int) name.toCharArray()[i]; // 아스키코드 형변환
			if (temp > 78) {
				strArray[i] = 91 - temp; // Z가 1부터
			} else {
				strArray[i] = temp - 65; // A가 0부터
			}

		}
		int len = strArray.length;

		int min_move = len - 1;

		for (int i = 0; i < len; i++) {
			answer += strArray[i];
			// strArray[i] = 0; //문자 한개를 입력 완료하면 0으로
			int next = i + 1; // 다음 위치부터
			while (next < len && strArray[next] == 0) {
				// 다음 위치가 A라면 그 거리를 증가시킴
				next++;
			}
			min_move = Math.min(min_move, i + len - next + i);
		}
		answer += min_move;

		return answer;
	}

}

 

커서 이동의 최소값을 구하는게 감이 잘 안잡혀서 좀 오래 걸리긴 했지만...나름 괜찮게 푼 거 같다.

---

 

끝!!