조이스틱(프로그래머스, Lv2, Java)

1. 조이스틱

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱 | 프로그래머스

알고리즘 설명:

탐욕법으로 당장 가장 가까운 A가 아닌 값으로만 탐색해 나가면 된다.

• 현재 인덱스에서 좌우로 탐색을 진행하여 A가 아닌 값이 먼저 나온 곳으로 인덱스를 옮겨서 탐색을 진행한다.
• A가 아닌 경우를 찾으면 문자열을 A로 바꾸고 다시 탐색 되지 않도록 한다.
• 문자열 값 변경이 일어나지 않은 경우 => 전부 탐색된 경우(전부 A로 바꾸었기 때문) -> while문 스톱
  flag 변수를 하나 만들어 문자열을 변경하는 경우와 아닌 경우를 구분한다.
• 알파벳 개수 26의 반절인 13을 기준으로 그 밑에 알파벳이면 위로 아니면 아래로 카운팅을 해준다.
• 왼쪽에서 오른쪽으로 탐색하는 코드를 오른쪽에서 왼쪽으로 탐색하는 코드보다 먼저 두어 우선으로 탐색한다.

막혔던 지점:

• BBBAAAB와 같이 A가 아닌 값이 나왔다고 바로 인덱스를 옮기는 것이 아니라 전체적으로 A가 아닌 문자를 탐색해서 경로를 결정해야 하는 경우가 있는데, 이 경우는 탐욕법에서 벗어나기 때문에 무시하였다.
  -> 프로그래머스 통과

코드(Java)

package coding;

public class Joystick {
	public static int solution(String name) {
		char[] word = name.toCharArray();
		int answer = 0;
		int len = word.length;
		int nowIdx =0;
		boolean flag = true; // 변경이 있는 지 확인하는 플래그
		
		//변경이 없을 때 까지
		while(flag) {
			//왼쪽에서 오른쪽으로 가는 인덱스
			int leftToright = 0;
			//오른쪽에서 왼쪽으로 가는 인덱스
			int rightToleft = 0;
			
			//플래그 초기화
			flag = false;
			
			//A인 경우가 아닌 인덱스를 탐색
			for(int i=0;i<len;i++) {
				
				//인덱스가 범위를 넘어가지 않았을 때
				if(nowIdx+i<len)
					leftToright = nowIdx +i;
				//인덱스가 범위를 넘어갔을 때
				else
					leftToright = nowIdx +i - len;
				
				if(nowIdx-i>=0)
					rightToleft = nowIdx -i;
				else
					rightToleft = nowIdx -i + len;
				
				if(word[leftToright]!='A') {
					//i는 오른쪽으로 움직인 횟수이므로 answer에 더해줌
					answer += i;
					//위로 움직일지 아래로 움직일지
					if(word[leftToright]-'A'>13) answer += 26-(word[leftToright]-'A');
					else answer += word[leftToright] - 'A';
					//값을 A로 바꾸어주어 다시 탐색되는 경우가 없도록 한다.
					word[leftToright] = 'A';
					nowIdx = leftToright;
					//A가 아닌 경우가 존재하면 변화가 있는 것이므로 flag를 true로 바꾸어주어 변화가 있다고 알려줌
					flag =true;
					break;
				}else if(word[rightToleft]!='A') {
					//i는 왼쪽으로 움직인 횟수이므로 answer에 더해줌
					answer += i;
					if(word[rightToleft]-'A'>13) answer += 26-(word[rightToleft]-'A');
					else answer += word[rightToleft] - 'A';
					word[rightToleft] = 'A';
					nowIdx = rightToleft;
					flag = true;
					break;
				}
				
			}
			
		}
		return answer;
	}

	public static void main(String[] args) {
		System.out.println(solution("JAN"));
	}

}