개발자로 살아남기

오른쪽으로 가는것을 기준으로 잡고 풀었다. 좌, 우 이동만 가지고 얘기하자면, 현재 위치를 기준으로 왼쪽/오른쪽 거리를 계산했을 때, 한 번이라도 왼쪽 거리가 짧을 경우 name의 끝에서부터 빼면서 계산했다. 다른 사람의 풀이를 보면 엄청 쉽게 구현하던데 신기하다...

탐욕법은 매 순간마다 최적의 값을 찾는다. 탐욕법은 탐욕스러운 선택 조건과 최적 부분 구조 조건을 가지는 특징이 있는데, 탐욕스러운 선택 조건은 앞에서 내가 선택한 것이 이후의 선택에 어떠한 영향을 미치지 않는다는 조건이고 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다는 특징이 있다. 

이 문제에서는 인덱스 0 위치에서 왼쪽으로 갈 경우 문자열의 끝에 갈 수 있지만 문자열의 끝에서 오른쪽으로 갈 경우 인덱스 0위치로 갈 수 없다. 그래서 아래와 같은 결과가 나오게 된다.

ABAAAABAAAAAAAAAAAAB => 최적해 (13) / 실제 계산한 해 (19)

탐욕법 자체가 이미 지나온 길을 되돌아갈 수 없다고 하면 탐욕법이 맞는거 같기도하고.. 아리송하다.

public int solution(String name) {
    int answer = 0;
    int notA_Count = 0;
    int curCount = 0;
    int lastIndex = 0;
    char curChar = 'A';
    boolean leftSmallerThanRight = false;

    // A가 아닌 개수 및 A가 아닌 마지막 인덱스 구하기
    for(int i=0; i<name.length(); i++){
        if (name.charAt(i) != 'A'){
            lastIndex = i;
            notA_Count++;
        }
    }

    // 오른쪽으로 갈 수 있는 최대 구하기
    // 인덱스 0을 기준으로 왼쪽으로 갔을 때 몇번째 값이 A가 아닌지 확인 (0의 위치에서 왼쪽으로 갈 경우 거리값이 +1이 되어야 함)
    int leftCount = name.length() - lastIndex;
    int rightCount = 0;
    int curPos = 0;
    int upDownCount = 0;
    for(int i=0; i<name.length(); i++){
        curChar = name.charAt(i);
        if (curChar == 'A'){
            continue;
        }

        // i 위치에서 현재 위치를 빼면 오른쪽으로 몇 번 가야 A가 아닌 문자가 나오는지 알 수 있음
        rightCount = i - curPos;

        // A가 아닌 문자를 만나기 위해 오른쪽으로 간 횟수와 왼쪽으로 간 횟수를 비교
        // 왼쪽으로 간 횟수가 더 적을 경우 빠져나와 맨 오른쪽에서 왼쪽으로 진행하기 위해 빠져나옴
        if (rightCount > leftCount + curPos){
            leftSmallerThanRight = true;
            break;
        }
        else{
            answer += rightCount;
        }

        // 알파벳 구하기
        upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
        answer += upDownCount;

        // 현재 위치를 i번째로 옮김
        curPos = i;
        rightCount = 0;
        curCount++;
    }

    // 현재 위치에서 왼쪽으로 가는게 더 빠른 경우가 있을 때
    // 현재 위치부터 왼쪽으로 구해야 하니까 leftCount는 curPos 값으로 변경
    leftCount = curPos;
    if (leftSmallerThanRight){
        for(int i=name.length() - 1; i>=0; i--){
            if (notA_Count == curCount){
                break;
            }

            curChar = name.charAt(i);
            // A면 한 칸 이동
            if (curChar == 'A'){
                leftCount++;
                continue;
            }
            leftCount++;

            upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
            answer += upDownCount;
            answer += leftCount;
            leftCount = 0;
            curCount++;
        }
    }

    return answer;
}