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

프로그래머스 조이스틱

문제풀이

완전탐색 또는 그리디 인데 완전탐색은 너무 오래 걸릴 것 같아서 그리디로 시도했다.

• 현재 위치에서 가장 가까운 바꿔야할 자리를 찾는다.
  • 왼쪽으로 갔을 때와 오른쪽으로 갔을 때 이동 횟수가 같으면 오른쪽으로 이동해야 한다. 왼쪽으로 이동하면 어떤 케이스("BBAABBB")를 통과하지 못한다...
  • 그리디로 풀 때는 이런 조건들을 잘 생각해야겠다.
• 조이스틱을 위로 올린 것과 아래로 내린 것 중 덜 사용하는 것을 선택하여 목표 알파벳으로 바꾼다.

구현코드

class Solution {
    public int solution(String name) {
        int answer = 0;
		int cnt = 0;
		char[] nick = name.toCharArray();
        boolean[] check = new boolean[nick.length];
        
        for(int i = 0 ; i < nick.length ; ++i) {
        	if(nick[i] != 'A') {
        		cnt++;
        	} else check[i] = true;
        }
        
        int idx = 0;
        for(int i = 0 ; i < cnt ; ++i) {
        	if(check[idx]) {
        		int lidx = idx;
        		int ridx = idx;
        		int left = 0;
        		int right = 0;
        		
        		while(check[lidx]) {
        			if(lidx == 0) lidx = nick.length - 1;
        			else lidx--;
        			left++;
        		}
        		
        		while(check[ridx]) {
        			ridx = (ridx + 1) % nick.length;
        			right++;
        		}
        		
        		if(left > right) {
        			idx = ridx;
        			answer += right;
        		} else {
        			idx = lidx;
        			answer += left;
        		}
        	}
        	check[idx] = true;
        	answer += changeAlphabet(idx, nick);
        }
        return answer;
    }
	
    private int changeAlphabet(int i, char[] nick) {
        int up = nick[i] - 'A';
        int down = 'Z' - nick[i] + 1;
        
        if(up > down) {
            return down;
        } else {
            return up;
        } 
    }
}