[프로그래머스]탐욕법(Greedy) : 조이스틱 (level 2) (c++)

 

https://programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

 

참고한 블로그 : https://keepgoing0328.tistory.com/71

#include <string>
#include <algorithm>

using namespace std;

int solution(string name) {
    
    int len = name.size();
    int answer = 0;
    
    // 알파벳 바꾸는 횟수
    for (int i = 0; i < len; ++i)
    {
        // A가 아닌 문자면 상하 이동
        if (name[i] != 'A')
        {
            answer += min(name[i] - 'A', 'Z' + 1 - name[i]);
        }
    }

    // 이동하는 횟수 : 오른쪽으로만 이동했을 때와, 중간에 왼쪽으로 턴했을때 값을 비교
    int left_min = len - 1;
    for (int i = 0; i < len; ++i)
    {
        // A가 아닌 문자면 좌우 이동
        if (name[i] != 'A')
        {
            // 다음 A가 아닌 인덱스 구하기
            int next_idx = i + 1;
            while (next_idx < len && name[next_idx] == 'A')
            {
                ++next_idx;
            }

            // i 위치에서의 총 왼쪽 이동 횟수 구하기
            int left_move = i * 2 + len - next_idx;

            // 최소 이동횟수
            left_min = min(left_min, left_move);
        }
    }

    return answer += left_min;
}

 

www.colorscripter.com/info#e"

 

 

그리디 적인 풀이.. 아직 어렵다 ㅜㅜ

 

TIP

이 문제의 포인트는 ◀▶"이동 횟수"에 있었다. 

 

어떻게 이동하든, ▲▼ 상하 조작 횟수는 같다!

어차피 결과적으로 알파벳을 똑같도록 만들어주므로

 

따라서 'A'가 아닌 문자 위치에서 최소 이동횟수를 그때그때(=그리디) 계산해야한다

 

 

BABAAAABAB 을 예로 들어보자.

 

'A'가 아닌 문자에서 다음 'A'가 아닌 문자까지 이동하면서 움직여야 한다. 

일단 오른쪽으로 갔을때의 최소 이동횟수는

0부터 마지막 인덱스까지 쭉 오른쪽으로 가는 것이다.

 

그렇다면 왼쪽으로 갔을때의 최소 이동횟수는??

그때그때 다르다!!

 

다음 그림을 보자

i = 0일때. 왼쪽, 오른쪽. 어느쪽에 최대한 덜 이동할까?

0에서 2로 왼쪽으로 가는 방법은

◀를 한번눌러 맨 끝으로 간후, 거기서 next까지 왼쪽으로 가는 것이다.

이걸 거리로 계산하면 len - next가 된다.

 

 

 

i = 2일때. 8까지 이동하려면 최소 이동거리는?

 

다음 i가 2일때를 보면

왼쪽으로 이동했을 때 총 이동거리

= 0부터 i까지 이동해온 거리 + 다시 0으로 가는 거리 + 끝에서 next까지 가는 거리

= i * 2 + (len - next)

 

 

i = 8일때. 10까지 이동하려면 최소 이동거리는?

 

i = 8일때도 마찬가지이다. 

 

 

i = 10일때. 11(?)까지 이동하려면 최소 이동거리는?

 

i = 10(마지막 인덱스) 일때도 마찬가지이지만, 다만 len - next 가 0이 된다.

 

 

이렇게 구한 각각의 이동거리들 중 최소의 값을 구하면

최소 이동횟수 완성!