木の棒

🔗 質問リンク

インプリメンテーションコード

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        int min_move = len-1; //조이스틱을 움직여서 가질 수 있는 가장 큰 이동값 = 차례로 움직여서 len까지 가는 경우 
          
        for(int i=0;i<len;i++){
            //알파벳 조작 값 계산
            answer += Math.min(name.charAt(i)-'A','Z'-name.charAt(i)+1);
           
            //최소 이동 값 계산 
            int next = i+1;
            while(next<len&&name.charAt(next)=='A') next++;
          
            min_move = Math.min(min_move,i+len-next+i);
           
        }
        
        answer += min_move;
        
        return answer;
    }
}

左→右にまっすぐ行く場合ではなく、帰りの基準をどうやって作るか分からないので、解決できなかった問題です.他のブログを見て参考にして、やっと理解できましたㅠ

アルゴリズム

min move:ゲームレバーを移動したときに得られる最大移動値。 左から右に1回移動すると最大になるのでlen-1。 ドア回りの場合は、アルファベット操作値と最小移動値を計算する必要があります。 1.アルファベット操作値（上下移動） (アルファベット-A)(down)と(Z-アルファベット+1)(up)の最小値を答えに追加します。 2.最小移動値（左右移動） 現在の文字の次の文字がAの場合、next++ 最終nextは、A文字の位置ではなくAを指す。 min move値と(i*2)+len-next値の最小値を答えに加算します。

(i*2)+len-next ?? 左->右に移動するのではなく、位置を左に移動します(逆)。 len-next:全長で、現在直後のAが余剰文字数を超えた i:右から右への移動回数 i*2+len-next:現在に戻り、残りの移動回数に戻る

実は私(i*2)+len-next部分は長い間考えていました...!ううう
私はコミュニティの多くの人がこの問題がグリディかどうかを論争しているのを見た.
実は知りません.ウハハ...アルゴリズム初心者なので…努力する

リファレンス

木の棒