34. 조이스틱⁂

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

조이스틱
탐욕법(Greedy) 
2562명 완료

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

문제의 출처: https://commissies.ch.tudelft.nl/chipcie/archief/2010/nwerc/nwerc2010.pdf

'완전 탐색'으로 풀어보았습니다.

문자를 찾을 때 마다 재귀를 이용해 전방 탐색과 후방 탐색을 반복합니다.  
각각의 재귀 함수에 따라갈 checkers 리스트는 [:]을 이용해 얕은 복사를 해줘야 합니다. 

def solution(name):
    def left_right(checkers, position, path_length):
        nonlocal min_path_length
        checkers[position] = False
        if not any(checkers):
            min_path_length = min(path_length, min_path_length)
            return
        for i in range(1, len(checkers)):
            j = (position + i) % len(name)
            if checkers[j]:
                left_right(checkers[:], j, path_length + i)
                break
        for i in range(-1, -len(checkers), -1):
            j = (position + i) % len(name)
            if checkers[j]:
                left_right(checkers[:], j, path_length - i)
                break

    answer = 0
    checkers_ = [False] * len(name)
    min_path_length = float("inf")
    for index, letter in enumerate(name):
        if letter != 'A':
            answer += min(ord(letter) - ord('A'), ord('Z') - ord(letter) + 1)
            checkers_[index] = True
    left_right(checkers_, 0, 0)
    return answer + min_path_length

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.06ms, 10MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.28ms, 10.2MB)
테스트 5 〉	통과 (1.39ms, 10.1MB)
테스트 6 〉	통과 (0.07ms, 10.3MB)
테스트 7 〉	통과 (0.32ms, 10.1MB)
테스트 8 〉	통과 (0.02ms, 10MB)
테스트 9 〉	통과 (0.07ms, 10.1MB)
테스트 10 〉	통과 (0.01ms, 10.1MB)
테스트 11 〉	통과 (0.03ms, 10MB)

파이썬 리스트의 마이너스 인덱스와
음수의 나머지 연산의 특징을 이용했습니다. 

파이썬에서 음수의 '%' 연산은 어떤 식으로 작동할까요? 
https://foxtrotin.tistory.com/97

 

자바

class Solution {
    int min_path_length = Integer.MAX_VALUE;

    boolean check_all_false(boolean[] checkers) {
        for (var each : checkers)
            if (each) return false;
        return true;
    }

    void left_right(boolean[] checkers, int position, int path_length) {
        checkers[position] = false;
        if (check_all_false(checkers)) {
            min_path_length = Math.min(min_path_length, path_length);
            return;
        }
        for (var i = 1; i < checkers.length; i++) {
            var j = (position + i) % checkers.length;
            if (checkers[j]) {
                left_right(checkers.clone(), j, path_length + i);
                break;
            }
        }
        for (var i = -1; i > -checkers.length; i--) {
            var j = (checkers.length + position + i) % checkers.length;
            if (checkers[j]) {
                left_right(checkers.clone(), j, path_length - i);
                break;
            }
        }
    }

    public int solution(String name) {
        int answer = 0;
        var checkers = new boolean[name.length()];
        for (var i = 0; i < name.length(); i++) {
            if (name.charAt(i) != 'A') {
                checkers[i] = true;
                answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            }
        }
        left_right(checkers, 0, 0);
        return answer + min_path_length;
    }
}

테스트 1 〉	통과 (0.04ms, 75.9MB)
테스트 2 〉	통과 (0.06ms, 74MB)
테스트 3 〉	통과 (0.04ms, 73MB)
테스트 4 〉	통과 (0.16ms, 75.3MB)
테스트 5 〉	통과 (0.59ms, 82.7MB)
테스트 6 〉	통과 (0.06ms, 72.9MB)
테스트 7 〉	통과 (0.17ms, 70.8MB)
테스트 8 〉	통과 (0.04ms, 79.1MB)
테스트 9 〉	통과 (0.05ms, 73.5MB)
테스트 10 〉	통과 (0.04ms, 73.9MB)
테스트 11 〉	통과 (0.04ms, 72.3MB)