[Programmers/CodingTest/Python]JOYSTIC

5346 ワード
coding test programmers python テキストリンク

問題の説明


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

せいげんじょうけん

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

    • I/O例

    name		return
"JEROEN"	56
"JAN"		23

    方法


    この問題はGRADYアルゴリズムに分類される.最初は状況全体を探るべきだと思っていましたが、グリディに分かれている以上、グリディで説明することにしました.まず、アルファベットを必要なアルファベットに変換する最小回数.重要なのは、whileゲートを介して変更された回数リストを巡回し、右側と左側の0ではなく、より速い方向に座標を移動する次の方向を見つけることです.
    グリディアルゴリズムは当時の状況での最適選択アルゴリズムであり、常に最適値が見つからない場合があり、この問題では常に最適値を見つけることが要求されている.GRADY方式で正解を得るのは難しいと判断し、74.1点で終了した.

    solution.py

    def solution(name):
    answer = 0
    press_button=[min(ord(word)-ord("A"), ord("Z")-ord(word)+1) for word in name]
    cur=0
    while True:
        answer+=press_button[cur]
        press_button[cur]=0
        l, r=1, 1
        if press_button==[0]*len(name):
            break
        while press_button[cur-l]==0:
            l+=1
        while press_button[cur+r]==0:
            r+=1
        if r>l:
            answer+=l
            cur=(cur-l)
        else:
            answer+=r
            cur=(cur+r)
    return answer
    C#判定(switch文詳細)
    サービスインタフェースのドキュメントの取得