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

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

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

문제풀이

조이스틱을 이용하여 주어진 단어를 만드는 최소이동 값을 구하는 문제이다. (놓친 부분이 많아 오래 걸렸다..)

 

처음 문제를 읽고 왼쪽, 오른쪽 방향으로만 생각해서 풀었다. 예상하지 못한 예외사항이 있었음..

 

EX) AXAAX의 경우 한쪽 방향만을 고려한다면

오른쪽으로만 이동한 경우 0 -> 1 -> 4 순으로 진행된다. (값은 8)

왼쪽으로만 이동한 경우 0 -> 4 -> 2 순으로 진행된다. (값은 8)

하지만 최적의 경로는 0 -> 1 -> 4인데 1에서 다시 왼쪽으로 가는 루트가 빠르다. (값은 7)

 

완전탐색을 이용하였다. 변환 할 값이 남았을 경우 왼쪽, 오른쪽 두 방향에 대해서 모든 결과를 구했다. 

 

소스코드

function solution(name) {
	var count = findNotA(name);
	var answer = 26 * 20;
	var alphabet = [];
	var alphabetIdx = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	var visited = new Array(name.length);
	visited.fill(0);
	for (var i = 0; i < 26; i++) {
		if (i <= 13) {
			alphabet.push(i);
		}
		else {
			alphabet.push(26 - i);
		}
	}
	function findNotA(name) {
		var count = 0;
		for (var i = 0; i < name.length; i++) {
			if (name[i] !== "A") {
				count++;
			}
		}
		return count;
	}

	function findRightNextPos(cur)
	{
		var idx = (cur + 1)%name.length;
		var dist = 1;
		while(cur != idx) {
			if (visited[idx] != 1 && name[idx] != 'A') {
				return dist;
			}
			dist++;
			idx++;
			idx = idx%name.length;
		}
		return -1;
	}

	function findLeftNextPos(cur)
	{
		var idx = cur -1 < 0 ? name.length - 1 : cur - 1;
		var dist = 1;
		while(cur != idx) {
			if (visited[idx] != 1 && name[idx] != 'A') {
				return dist;
			}
			dist++;
			idx--;
			if (idx < 0) {
				idx = name.length - 1;
			}
		}
		return -1;
	}

	function solve(cur, depth, sum) {
		if (depth + 1 == count) {
			sum = sum + alphabet[alphabetIdx.indexOf(name[cur])];
			if (answer > sum) {
				answer = sum;
			}
			return;
		}

		
		var curVal = 0;
		var checked = false;
		if (name[cur] !== 'A') {
			curVal = alphabet[alphabetIdx.indexOf(name[cur])];
			checked = true;
		}
		sum += curVal;
		visited[cur] = 1;
		var right = findRightNextPos(cur);
		if (right != -1) {
			var next = (cur + right) % name.length;
			solve(next, checked ? depth + 1 : depth, sum + right);
		}
		var left = findLeftNextPos(cur);
		if (left != -1) {
			var next =  cur - left;
			if (next < 0) {
				next = name.length + next;
			}
			solve(next, checked ? depth + 1 : depth, sum + left);
		}
		visited[cur] = 0;		
	}
	solve(0, 0, 0);
    return answer;
}