시작하며 🔥

으, 화나네요!
풀자마자 드는 생각은 이게 과연 그리디일까 싶었어요.
왜냐하면, 현재의 최적의 답안이, 곧 해로 접근할 수 있는 과정이 아니었기 때문이죠.
질문란을 보니, 꽤나 많은 사람들이 공감을 했었네요. 네, 이건 엄연히 말하자면 그리디가 아닙니다.

결국, 허탈함에 우선순위 큐로 풀었어요...ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그나마 한 방에 풀리지 않았다면, 멘탈이 바사삭이었을 듯합니다.

그래도, 이 문제는 꽤나 접근하기 까다로웠어요. 저한테는 말이죠.
그 과정을, 지금부터 살펴보겠습니다.

풀이 과정 📃

이게 과연 그리디인가 싶었을 때, 아차 싶어서 좀 더 유연한 사고를 하자고 생각하며 다른 방식으로 풀었습니다.
그때의 제 뇌리 속의 과정은 다음과 같았어요.

1. 결국에 이 문제의 핵심은 인덱스를 어느 방향으로 접근하는 것이 가장 최소 횟수로 접근할 수 있느냐를 묻는 것이다.
2. 따라서, 인덱스를 접근하는 횟수와 알파벳을 바꾸는 횟수를 따로 분리해서 접근한다. ⭐
3. 먼저 알파벳을 바꿀 때마다 인덱스를 어떤 배열에 담는다.
4. 이때, 우선순위 큐에 넣기 전에 어떤 indexArr(바꿀 인덱스 값들을 담아놓은 배열)의 크기를 살펴보자.
   4-1. if (indexArr.length === 0) return 0이다. 바꾼 게 없기 때문이다.
   4-2. if (indexArr.length >= 1) 인덱스 양에 따라서 가장 앞쪽 인덱스와 가장 뒤쪽 인덱스에 맞춰 (현재 이동 횟수, 현재 위치, 앞으로 남은 indexArr)을 우선순위 큐에 넣는다.
5. 우선순위 큐에서 앞으로 남은 indexArr가 빈 배열이 리턴될 때까지 4-2번을 반복한다. 만약 이를 만족하면 최소 횟수를 가져온다.
6. 알파벳 치환 횟수 + 리턴된 인덱스 접근 최소 횟수를 리턴한다.

class MinHeap {
    constructor() {
        this.heap = [null];
    }
    updateParentIndex(index) {
        return Math.floor(index / 2);
    }
    updateIndices(index) {
        return [ index, index * 2, index * 2 + 1]
    }
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    heappush(val) {
        this.heap.push(val);
        let nowIndex = this.heap.length - 1;
        let parentIndex = this.updateParentIndex(nowIndex);
        while(nowIndex > 1 && this.heap[parentIndex][0] > this.heap[nowIndex][0]) {
            this.swap(nowIndex, parentIndex)
            nowIndex = parentIndex;
            parentIndex = this.updateParentIndex(nowIndex);
        }
    }
    heappop() {
        if (this.heap.length === 1) return;
        if (this.heap.length === 2) return this.heap.pop();
        const min = this.heap[1];
        this.heap[1] = this.heap.pop();
        let [ nowIndex, leftIndex, rightIndex ] = this.updateIndices(1);
        if (!this.heap[leftIndex]) return min;
        if (!this.heap[rightIndex]) { 
            if (this.heap[leftIndex][0] < this.heap[nowIndex][0]) {
                this.swap(leftIndex, nowIndex);
            }
            return min;
        }
        while ((this.heap[leftIndex][0] < this.heap[nowIndex][0]) || (this.heap[rightIndex][0] < this.heap[nowIndex][0])) {    
            const minIndex = this.heap[leftIndex][0] <= this.heap[rightIndex][0] ? leftIndex : rightIndex;
            this.swap(nowIndex, minIndex);
            [ nowIndex, leftIndex, rightIndex ] = this.updateIndices(minIndex);
            if (!this.heap[leftIndex]) return min;
            if (!this.heap[rightIndex]) { 
                if (this.heap[leftIndex][0] < this.heap[nowIndex][0]) {
                    this.swap(leftIndex, nowIndex);
                }
                return min;
            }
        }
        return min;
    }
    print() {
        console.log(this.heap)
    }
    getLength() {
        return this.heap.length;
    }
}

const getMinChangeCount = (before, after) => {
    const count = Math.abs(before.charCodeAt(0) - after.charCodeAt(0));
    return Math.min(count, 26 - count);
};
const createPushedArr = (name, beforeCount, nowIndex, nextIndex, arr) => {
    const count = Math.max(nowIndex, nextIndex) - Math.min(nowIndex, nextIndex);
    return [beforeCount + Math.min(count, name.length - count), nextIndex, arr.filter(value => value !== nextIndex)]
}
const getResult = (name, minHeap) => {
    while(true) {
        const [cnt, idx, arr] = minHeap.heappop();
        if (arr.length === 0) return cnt;
        if (arr.length >= 1) {
            if (arr.length > 1) minHeap.heappush(createPushedArr(name, cnt, idx, arr[arr.length - 1], arr))
            minHeap.heappush(createPushedArr(name, cnt, idx, arr[0], arr))
        }
    }
}

const solution = name => {
    let answer = 0;
    const indexArr = [];
    const minHeap = new MinHeap();
    for (let i = 0; i < name.length; i++) {
        const now = name[i];
        if (now !== 'A') {
            if (now !== 0) indexArr.push(i); // 현재 가야 할 인덱스 번호 넣기
            answer += getMinChangeCount('A', now);
        }
    }
    // [ 목표 인덱스로 갔을 때 횟수, 간 결과 인덱스 위치, 남은 인덱스]
    if (indexArr.length === 0) return 0;
    if (indexArr.length >= 1) {
        if (indexArr.length > 1) minHeap.heappush(createPushedArr(name, 0, 0, indexArr[indexArr.length - 1], indexArr))
        minHeap.heappush(createPushedArr(name, 0, 0, indexArr[0], indexArr))
    }
    answer += getResult(name, minHeap);
    return answer;
}

마치며

15점을 주는군요. 이게 난이도에 따라서 주는 건지 잘 모르겠지만, 적어도 제게 꽤나 난이도가 적지 않았네요. (그리디라는 말만 아니었으면 오히려 더 쉬웠을지도...?)
일단 프로그래머스는 테스트케이스가 꽤나 약한 것 같아요. 이부분은 차차 고쳐졌으면 합니다..!

여튼, 아닌 새벽에 머리가 땡겼던 문제. 심지어 힙 구현도 JS라 어지간히 힘드네요. 😂 그래도 이제는 안 보고도 쓸 정도로 이해를 확실히 할 수 있게 됐어요!
가까스로 홀로 클리어해낸다는 게 참 기쁘고, 정말 다행이에요 😋👍

++++

저는 혹여나 만약 오른쪽 조이스틱 이동이 마지막 위치에서 첫번째 위치로 갈 수 있다는 가정하에 작성했어요. 만약 이것이 불가하다면, createPushedArr 부분을 바꿔주면 되겠죠?!

혹여나 나중에 업데이트 돼서 이 글이 💩글이 될 수도 있으니, 이 부분 유의해주세요~