문제 푼 날짜 : 2021-10-05

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42860

접근 및 풀이

그리디 알고리즘으로 푸는 문제였다.
그리디라는 것을 알고 풀었음에도 구현하는데 애를 먹었다.
처음에 시작점에서 조이스틱을 좌우로 움직인 직후 바로 상하를 움직이는 방식으로 구현하려고 했으나, 결과적으로 뜻대로 구현하지 못하였다.
그래서 조이스틱의 상하 움직임과 좌우 움직임을 분리하여 최소 이동횟수를 구해주었다.
상하 움직임은 'A' 아스키코드 값에서 조이스틱 위치에 있는 알파벳의 아스키코드 값의 차이를 이용하여 구해주는데, 조이스틱을 위로 움직여 'A'를 만드는 것은 'A' + 26에서 빼주었고, 아래로 움직여 'A'를 만드는 것은 해당 알파벳에서 'A'값을 빼주었다. 이 중 최솟값만을 찾아 더해주었다.
좌우 움직임이 중요했다. 처음에는 어느 방향이든 한 쪽으로 쭉가는것이 최적해라고 생각했는데, 이것은 잘못된 생각이었다. 예를들어, BBBAAAAAAAAC 라는 입력이 주어지면, 한 방향으로 가는 것이 정답이 아니다. 만약 한쪽으로만 쭉 이동하면 11이라는 이동값이 구해지지만, 인덱스를 기준으로 0(B)->11(C)->0(B)->1(B)->2(B) 와 같이 이동한다면 11보다 훨씬 작은 4라는 값으로 이동이 가능하기 때문이다. 이 점을 고려하지 못했다면 조금 어렵게 느껴질 수 있는 문제였다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    
    int idx = -1;
    int move = name.length() - 1;
    for (int i = 0; i < name.length(); i++) {
        char ch = name[i];
        if (ch == 'A') {
            idx = i;
            while (name[idx] == 'A' && idx < name.length()) { // 연속되는 'A' 찾아주기
                idx++;
            }
            int fromLeft = max(0, i - 1); // 문자열 시작점에서 연속된 'A' 시작지점까지 거리
            int fromRight = name.length() - idx; // 문자열 끝지점에서 연속된 'A' 끝지점까지 거리
            move = min(move, fromLeft + fromRight + min(fromLeft, fromRight));
        }
    }
    answer += move;
    
    for (int i = 0; i < name.length(); i++) {
        answer += min(name[i] - 'A', 'A' + 26 - name[i]);
    }
    return answer;
}

결과

피드백

level2 였지만 간단하지 않고 생각을 충분히 해야하는 좋은 문제였던 것 같다.