탐욕법(Greedy)_조이스틱

요즘 그리디가 너무 안 풀리는것 같다 ㅠㅠ 마지막 A의 위치에 따라 조이스틱 좌우 방향을 결정 짓는 부분에서 오래걸렸다...

결국 블로거님을 참고하여서 경우의 수를 알았다..

• 4가지 경우의 수

1. ▶ (): 뒷부분이 A인 경우 최소
2. Ex) BBBBAA이면 오른쪽으로 3번만 이동하면 됨
3. ◀ :앞부분이 A인 경우 최소
4. Ex) AAAAABBB이면 왼쪽으로 3번만 이동하면 됨
5. ▶◀ : 중간에 A가 많은 경우 중 앞부분에 A가 아닌 알파벳이 더 적은 경우
6. Ex) BBBAAAAAAAAABBBBB이면 오른쪽으로 2번, 왼쪽으로 2 + 5번. 즉, 2 * 2 + 5 = 9번만 이동하면 됨
7. ◀▶ : 중간에 A가 많은 경우 중 뒷부분에 A가 아닌 알파벳이 더 적은 경우
8. Ex) BBBBBBBAAAAAAAAABBB이면 왼쪽으로 3번, 오른쪽으로 3 + 6번. 즉, 3 * 2 + 6 = 12번만 이동하면 됨

이 4가지 경우의 이동 횟수를 세기 위해 front, back, half_front, half_back 변수를 사용하였다.

 

출처: https://mind-devlog.tistory.com/6 [Min:D's Devlog]

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

map<char, int> mp;
int solution(string name) {
    int answer = 0;
    int len = name.size();
    int mid = len / 2; 
    int front = 0; 
    int back = 0; int half_front = 0; int half_back = 0;

    for(int i=0; i<26; ++i){
        mp['A'+i] = i;
    }
    for(int i=0; i<name.size(); ++i){
        if(name[i]<='N'){
            answer = answer + mp[name[i]];
        }
        else{
            answer = answer + (26 - (mp[name[i]]));
        }
        if (name[i] != 'A') { 
            front = i; 
            if (i <= mid) 
                half_front = i; 
        } 
        if (name[len - i] != 'A') { 
            back = i; 
            if (len - i > mid) 
                half_back = i;
        }
    } 
    answer += min(min(front, back), min(half_back * 2 + half_front, half_front * 2 + half_back));
    
    return answer;
}