[JS/Programmers] 조이스틱 - Greedy 알고리즘 활용하기

문제: 조이스틱

해결 과정

그리디 알고리즘의 특성을 고려하여, 우선 필요한 작업부터 수행해 나가는 것이 좋다.(=당장의 최적합을 찾기)

1. 최초값인 A를 기준으로, 알파벳의 중간 지점인 N을 기준으로

   1) 다음 알파벳으로 올라가는 것	2) Z부터 역순으로 내려가는 것

   중 최솟값을 선택한다.
   이때, 알파벳의 ASCII 코드를 찾아내는 함수인 charCodeAt()을 활용하기!

count += Math.min((name[i].charCodeAt(0) - 65), (91 - name[i].charCodeAt(0)));

2. 다음 문자에 연속된 A가 있는지 판단하기 위해, while 반복문을 사용하여 연속된 가장 마지막 A를 찾는다.

let nextA = i + 1;
while(nextA < name.length && name.charCodeAt(nextA) === 65) nextA++;

3. 다음 문자로 이동할 때, 앞으로 가는 것이 빠른지, 혹은 뒤로 가는 것이 빠른지를 판단한다.
   이때, A가 연속으로 나올 경우, 굳이 그쪽 끝까지 갔다가 다시 돌아오는 것보다, 미리 돌아서 다른 방향으로 가는 것이 더 효율적일 수 있는데, 그 비용을 i * 2로 설정해 준다.

min = Math.min(min, (i * 2) + name.length - nextA, i + (name.length - nextA) * 2);

최종 답안

function solution(name) {
    var count = 0;
    let min = name.length - 1; //좌우 이동 최초 최소값
    for(let i = 0; i < name.length; i++){
      //위아래 버튼 여부 결정
        count += Math.min((name[i].charCodeAt(0) - 65), (91 - name[i].charCodeAt(0)));
        let nextA = i + 1; //A의 연속 개수를 고려한 좌우 이동 여부 결정
      	//연속된 A 개수 찾기
        while(nextA < name.length && name.charCodeAt(nextA) === 65) nextA++;
      // 그냥 좌로만 쭉 가는 거랑, 우로 한번 거쳐서 맨 뒤로 가는 거, 뒤로 간 후 앞으로 돌아오는 것 중에서 최소값 비교
        min = Math.min(min, (i * 2) + name.length - nextA, i + (name.length - nextA) * 2);
    }
    return count + min;
}

Greedy 알고리즘

그리디 알고리즘이란, 선택해야 하는 상황에서 순간순간 보이는 가장 최적화된 결과를 선택하여 최종 결과에 도달하는 것이다. 이러한 특징은 곧 빠른 실행 속도를 보장하는데, 맹점은 이러한 알고리즘이 무조건 최적의 결과를 보장하지는 않는다는 것이다.

• 그리디 알고리즘의 주요 특징

  1. 이전의 선택이 이후의 선택에 영향을 주지는 않는다.
  2. 하나의 큰 문제는 여러 개의 작은 문제들로 분리되며, 이 결과는 작은 문제들의 최적화된 해결 방법으로 결정된다.