[programmers]欲張り法(Greedy):JOY STIC

8263 ワード
programmers Programmers-Greedy：JOY STIC テキストリンク
コードテスト練習-Joycastic|プログラマー

📌 質問する


問題の説明


JOYSTICでアルファベット名を完成最初はAのみで構成されていましたex)完成する名前は3文字AAA、4文字AAAAAA
JOYロッドを各方向に移動し、以下のようにします.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀︎ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶︎ - 커서를 오른쪽으로 이동
たとえば、次の方法でJAZを作成できます.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
パラメータとして名前を作成する場合は、名前に対するJOYSTIC操作回数の最大値を返すソリューション関数を作成します.

制限

  • nameはアルファベットの大文字のみで構成されています.
  • nameの長さは1または20以下です.

    • 211 I/O例


    namereturn"JEROEN"56"JAN"23

    📌 に答える


  • 私のやり方(エラーX)
    上下操作については,何度変更しても関係ないので,左右操作がコアであると考えられる.
    したがって、現在位置が変更されていない文字では、右に最も近い位置に移動する距離と、左に最も近い位置に移動する距離とを比較して、最も近い位置に移動する距離と考えられ、次に問題に近づき、解決した.ここで2つの問題が発生した.
    1つ目の問題は、最も右に近い距離と最も左に近い距離が同じであれば、どちらに行けばいいですか?2つ目の問題は、左に無限に移動できるが、文字列の末尾に右に着いても、再び1つ目に戻ることはないということだ.
    最初の問題を解決するために、距離が等しい場合、左側は次の文字列の方向を変更する必要があるかどうかを決定し、不要な方向を先に移動してから変更します.しかし、ここで2番目の問題の部分は問題を引き起こします.距離が同じ場合、文字列の最後の方向に左に移動すると、再び右に移動することは許されないため、左に移動し続ける現象が発生し、無条件に修正要素の少ない方向に移動する要求にも合致しない.
    最終的に他人の解答を見た.

  • 他人のやり方
    上下操作は他の影響を受けないため、文字を比較して移動回数を増やすだけで行われ、左/右操作では真の移動に対して移動回数を増やす概念よりも文字列を変えるために移動する経路長の概念である.
    たとえば、ABAAAABBを作成する必要がある場合、デフォルトでは、最初の位置から最後の方向に移動する値문자열 길이 - 1、すなわち7に設定されています.次に、各位置を基準として、その位置まで右に移動したテキストを左に移動し、作成時に最大移動距離を求めます.
    1番目の位置では、1番目のAから2番目のBまで、全部で7回左に移動します.2番目の位置では、1マス目から2番目の位置まで右に移動し、3回左に移動すると文字列が完成します.
    中間3位から6位までの4文字がAなので変更する必要はありません.つまり、2番目の位置であれば、文字列を完了するために合計4回しか移動できません.
    このようにして最後のビットまで計算すると、右に2番目のビットまで移動する場合が最も少なく、文字列が完成する.

    • 💻 インプリメンテーション

    public class Joystick {

    public static void main(String[] args) {
        String name = "ABAAAABB";
        System.out.println(new Solution().solution(name));
    }

    static class Solution{

        public int solution(String name){
            int answer = 0;
            int len = name.length();

            int min = len - 1;

            for (int i = 0; i < len; i++) {
                char c = name.charAt(i);
                int mov = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1);
                answer += mov;

                int nextIndex = i + 1;
                while (nextIndex < len && name.charAt(nextIndex) == 'A')
                    nextIndex++;

                min = Math.min(min, (i * 2) + len - nextIndex);
            }

            answer += min;
            return answer;
        }
    }
}
    高同時テストでのいくつかの問題と解決
    Spring Boot Detoolsプラグインの使用