문제 링크

바로가기

문제 풀이

JS

function solution(name) {
    let answer = 0;
    const dict = {};

    // char 인덱스 정의
    const alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
    alphabet.map((idx, val) => dict[idx] = val);
    
    // 알파벳을 앞으로 돌지 뒤로 돌지 판별
    for(const word of name) 
        answer += Math.min(dict[word], Math.abs(26 - dict[word]));
    
    // 경우의 수 1. 그냥 순회 2. 오른쪽으로 갔다가 뒤로 가기 3. 왼쪽으로 갔다가 오른쪽으로 가기
    let move = name.length - 1; // 1번
    let j = 0;
    for(let i = 0; i < name.length; ++i) {
        j = i + 1; // 현재 인덱스 다음부터 A가 아닌 인덱스
        while(j < name.length && dict[name[j]] === dict['A']) j++;
        move = Math.min(move, Math.min(i + i + (name.length - j), (name.length - j) + (name.length - j) + i))
    }
    
    return answer + move;
}

PY

def solution(name):
    answer = 0
    
    move = len(name) - 1
    y = 0
    for idx, word in enumerate(name):
        answer += min(ord(word) - ord('A'), abs(ord('Z') - ord(word) + 1))
        y = idx + 1
        while y < len(name) and name[y] == 'A': y += 1
        move = min(move, min(idx + idx + len(name) - y, len(name) - y + len(name) - y + idx))

    return answer + move

풀이

탐욕법은 너무 어렵다..
먼저 탐욕법은 여러 가지 경우의 수를 생각해서 최소의 경우를 구하는 방법이다.
탐욕법을 풀면서 팁은 여러 가지 경우의 수를 판단한 다음 최솟값 구하는 메서드를 사용하는 것이다.

먼저, 두 개의 과정을 거쳐야한다.

1. 알파벳을 앞으로 카운트할지 뒤로 카운트할지
2. 문자를 오른쪽으로 갈지 왼쪽으로 갈지

첫 번째 과정은 쉽다.
문자가 26개가 있으니 앞으로 카운트한 것과 뒤로 카운트한 것의 최솟값을 구하는 것

두 번째 과정이 정말 어려웠다.
두 번째 과정은 세 개의 경우의 수가 있다.

1. 가장 쉬운 그냥 순서대로 체크
2. 오른쪽으로 갔다가 왼쪽으로 가는 경우
3. 왼쪽으로 갔다가 오른쪽으로 가는 경우

모든 문자를 순회하면서 세 가지의 경우의 수를 체크해주어야한다.
일단 현재 인덱스와 현재 인덱스 다음으로 오는 A가 아닌 문자를 체크한다.
그 다음 현재 인덱스에서 위 세 가지의 경우의 수를 구하고 비교를 한다.

그 다음 두 개의 과정에서 얻은 수를 더하면 결과값이 나온다.

새롭게 배운 점

1. 자바스크립트에서 아스키코드 값을 얻으려면 charCodeAt, 파이썬에서는 ord 메서드를 사용한다.