탐욕법(Greedy) > 조이스틱

[ 문제설명 ] 

 

---

[ 풀이과정 ] 

하 씨 어려워ㅠ

알파벳 이동 조이스틱은 그냥 반복문 돌면서 따로 구해서 더하구

이거 포인트는 좌우 이동 횟순데

중간에 A로만 이뤄진 문자열 없으면 문자열 길이-1 이 이동횟수고

아니면 왼쪽오른쪽 왔다갔다 해야되는데 left+right+min(left,right)가 되겠지 뭐

여기서 left는 A문자열 기준 왼쪽으로 가는거 right는 오른쪽인데 왼쪽은 A문자열 시작 위치기준이고 오른쪽은 전체 길이에서 A문자열 길이+위치 뺀만큼이겠지

이거 고민하는데 머리 터질뻔 사실 구글링함ㅋ

암튼 아래가 내 코드ㅠ

 

---

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string name) {
    int answer = 0;
    int move = name.length()-1;
    int aa=0;
    for(int i=0;i<name.length();i++) //알파벳 변경 횟수
    {
        if(name[i]!='A')
        {
            answer+=min(name[i]-'A','Z'-name[i]+1);
        }
    }
    
    for(int i=0;i<name.length();i++)
    {
        if(name[i]=='A')
        {
            int target = i;
            while(target<name.length() && name[target] == 'A')
            {
                target++;
            }
            int left= i==0 ? 0 : i-1;
            int right = name.length()-target;
            move=min(move,left+right+min(left,right));
        }
    }
    answer+=move;
    return answer;
}