[Java/프로그래머스/탐욕법(Greedy)] Level 2: 조이 스틱

문제

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

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

 

코드

조이스틱을 위 아래로 조작하는 것과 좌우로 조작하는 것을 나누어 생각했다.

상하는 쉽게 해결됐지만 좌우는 탐욕법으로 해결했다.

 

현재 위치(pos)에서 가장 가까운 바꿔야 할 자리를 찾는다.

→ 왼쪽으로 A 개수와 오른쪽으로의 A 개수를 비교한다. (만약 이동횟수가 같을 때, 오른쪽으로 이동해야 한다.)

 

• visited 배열
  • A가 있는 위치는 true로 바꾼다.
  • 현재 위치에서 좌우로 비교했을 때 더 짧은 경로를 true로 바꾼다.
• A가 아닌 원소 개수만큼 for문을 반복한다.
  • 만약 현재 위치(pos)가 visited가 true인 위치라면, (A이거나 이미 바꿨거나)
    • 좌우로 그냥 지나쳐야 하는 원소의 개수를 검사해본다.

 

class Solution {
    public int solution(String name) {
        int answer = 0;
        int notACnt = 0;
        boolean[] visited = new boolean[name.length()];
        //상하
        for(int i=0; i<name.length() ; i++){
            char presentAlpha = name.charAt(i);
            if(presentAlpha !='A'){
                if(presentAlpha <= 'N'){
                    answer += (presentAlpha-'A');
                }else{
                    answer += ('Z'-presentAlpha+1);
                }
                
                ++notACnt;
            }else{
                visited[i] = true;
            }
        }
        
        //좌우
        int pos = 0;
        for(int i=0; i<notACnt; i++){
            if(visited[pos]){
                int lIdx = pos;
                int rIdx = pos;
                int left = 0;
                int right = 0;
                
                while(visited[lIdx]){
                    if(lIdx == 0)
                        lIdx = name.length()-1;
                    else
                        --lIdx;
                    ++left;
                }
                while(visited[rIdx]){
                    rIdx = (rIdx+1)%name.length();
                    ++right;
                }
                
                if(left >= right){
                    pos=rIdx;
                    answer+=right;
                }else{
                    pos=lIdx;
                    answer+=left;
                }
            }
            visited[pos] = true;
        }
        
        return answer;
    }
}