[프로그래머스/탐욕법] 조이스틱

문제 링크

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

---

문제 설명

---

코드 전문

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string name) {
    int answer = 0;
    int length = name.length();
    int move = length - 1;

    for (int i = 0; i < length; i++) {
        answer += min(name[i] - 'A', 'Z' - name[i] + 1);
        
        int next = i + 1;
        while (next < length && name[next] == 'A') {
            next++;
        }
        
        move = min(move, min(i + i + (length - next), (length - next) + (length - next) + i));
    }

    answer += move;
    return answer;
}

---

풀이

며칠 간 못 풀어서 질문하기에 있는 풀이를 봤다.

https://school.programmers.co.kr/questions/76244

 

move는 오른쪽, 왼쪽 이동 횟수만 저장한다.

오른쪽으로만 진행했을 때 이동 횟수는 최대가 된다. 최댓값으로 초기화 해준다.

int move = length - 1;

 

위쪽, 아래쪽으로 이동하는 횟수를 answer에 더해준다.

answer += min(name[i] - 'A', 'Z' - name[i] + 1);

 

i의 오른쪽에 있는, A가 아닌 문자의 위치를 찾는다.

        int next = i + 1;
        while (next < length && name[next] == 'A') {
            next++;
        }

 

이제 두 가지 경우를 비교하여 최소로 이동하는 경우를 선택할 것이다.

 

1. 원점 기준 오른쪽으로 i만큼 이동 후 다시 왼쪽으로 이동해 뒤에서 부터 next를 탐색하는 경우

i + i + (length - next)

 

2. 원점 기준 왼쪽으로 이동해 맨 뒤에서 next까지 탐색하고 다시 오른쪽으로 이동해 i를 탐색하는 경우

(length - next) + (length - next) + i

 

두 경우 중 이동 횟수가 더 적은 것을 선택하고, move와 비교하여 더 작은 값을 골라 move에 저장한다.

move = min(move, min(i + i + (length - next), (length - next) + (length - next) + i));

 

그리고 move의 값을 answer에 더하면 끝!