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

programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

 

 조이스틱을 이용할 때, 일방적으로 왼쪽으로 가거나 오른쪽으로 가는 것이 끝이 아니다. 왼쪽으로 오른쪽으로 언제든지 최소이동을 위해 갈 수도 있음을 알아야 한다. 하지만 일방적으로 모두 왼쪽오른쪽으로 계속 완전탐색을 하는 것도 좋은 방법은 아니다. 엄청난 중복으로 인해서 시간초과가 나는 것이 당연하기 때문이다. 따라서 적절하게 case를 나누어주어야 한다. ( 이 문제의 결함은 테스트케이스가 최소이동을 잡을 수 없다.)

 

"BBBBAAAABA" 기댓값 12
"BBBBAAAAAB" 기댓값 10
"AABAAAAAAABBB" 기댓값 11
"AAB" 기댓값 2

A로 이루어진 단어에서 원하는 name에 도달하는 것이 아니라 name을 A로 이루어진 단어로 변환하도록 했다.

나는 기본적으로 dir을 통해서 왼쪽 , 오른쪽을 구분하였다. 특히 일반적인 이동에서는 왼쪽, 오른쪽을 다 가도록 한다. 이동을 할 때 A가 나온다면 특별하게 더 케이스를 나눈다. 왜냐하면 이미 A에서 수정을 하고 이동을 했는데, 불필요하게 다시 검사하는 행위를 피하기 위해서이다. 따라서, dir==0이면, A에서는 왼쪽(-1),오른쪽(1)을 가도록 만들었다. 이때 이동할 때 dir을 -1 ,1 로 잡았으므로 또 A가 나오면 자신이 이동하는 방향으로만 이동한다. 그렇다면, A를 만났을 때 완전탐색을 사용하는 것보다 테스트케이스가 훨씬 줄어든다.  

 

import java.util.*;
class Solution {
	String original = "";
	int answer = 0;

	public int solution(String name) {

		for (int i = 0; i < name.length(); i++)
			original += 'A';

		answer = 26 * name.length() + name.length();

		move(0, 0, 0, name);
		return answer;
	}

	// dir -1은 왼쪽, 0은 양쪽 다, 1은 오른쪽
	public void move(int index, int cnt, int dir, String line) {

		// 옮기기 전에 완성형일 수 있다.
		if (line.equals(original)) {
			if (cnt - 1 < answer)
				answer = cnt - 1;
			return;
		}

		if (cnt > answer)
			return;

		if (index < 0) {
			move(line.length() - 1, cnt, -1, line);
			return;
		}

		if (index == line.length()) {
			move(0, cnt, 1, line);
			return;
		}

		if (line.charAt(index) == 'A') {
			if (dir == 0) {
				move(index - 1, cnt + 1, -1, line);
				move(index + 1, cnt + 1, 1, line);
			}

			else if (dir == 1) {
				move(index + 1, cnt + 1, 1, line);
			}

			else if (dir == -1) {
				move(index - 1, cnt + 1, -1, line);
			}
			return;
		}

		// UP버튼을 눌러서 계산
		int up = Math.abs((int) ('A' - line.charAt(index)));

		// DOWN 버튼을 눌러서 계산
		int down = Math.abs((int) ('Z' - line.charAt(index))) + 1;

		int val = (up > down) ? down : up;

		cnt += val;

		String newLine = "";

		for (int i = 0; i < line.length(); i++) {
			if (i == index) {
				newLine += 'A';
			} else
				newLine += line.charAt(i);
		}

		move(index + 1, cnt + 1, 0, newLine);
		move(index - 1, cnt + 1, 0, newLine);

	}
}