[그리디] 프로그래머스 '조이스틱' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=javascript 

프로그래머스

2. 설명

이 문제는 연속되는 A의 처리(A 뭉텅이)가 가장 중요한 문제다. 이것 때문에 고민을 많이 했었고, 결국 답이 떠오르지 않아 구글링을 하였으며 로직 이해에도 꽤 오랜 시간이 걸렸다 ㅠㅠ

그리고 또 하나 중요한 것은 알파벳의 아스키코드다. A는 65이며 알파벳은 총 26개이므로 Z는 91이 된다.

이동 횟수의 총 합 = 좌/우 이동 횟수 + 상/하 이동 횟수

좌/우 최소 이동 횟수는 아래 세 가지를 비교하여 나온 최솟값이다.

1. 처음부터 끝까지 쭉 비교하는 경우

=> name.length

2. 처음부터 시작하다가 A 뭉텅이를 만났을 때, 다시 뒤로 가서 A 뭉텅이 끝난 이후 단어부터 시작하는 경우

=> i*2 + name.length - idx

ex) BBBAAAAAAABA

• i*2 : 다시 첫 단어로 돌아가는 횟수. 여기서는 첫번째 A까지 갔다가 뒤로 돌아가므로 2(i) * 2 = 4 // 4
• name.length - idx : 길이 - A 뭉텅이가 끝난 다음 단어의 위치 => 여기서는 12 - 10 = 2 // 2

3. 연속된 A의 앞쪽보다 뒷쪽이 짧은 경우, A 뭉텅이 길이 이용하여 맨 뒤에서 시작하는 경우

=>  i + 2 * (name.length - idx)

• 2 * name.length - idx : 'A 뭉텅이 끝난 다음 단어부터 비교하고 다시 맨 앞으로 돌아오는 횟수
  (맨 뒤 A-> 뒤에서 두번째 B(1번) -> A 뭉텅이 제일 마지막 A(2번) -> 뒤에서 두번째 B(3번) ->맨 뒤 A(4번)  // 4
• i : 다시 처음으로 돌아온 후 좌우 이동 횟수(B->B->B) // 2

function solution(name) {
  // 상하 이동 관련 변수
  let tb = 0;
  // (좌우 이동 관련 변수)최대로 많이 움직이는 경우는 길이만큼 이동이므로 길이 -1로 설정
  let lr = name.length - 1;

  [...name].map((n, i) => {
  	// 1. 상하 이동
    // 긱 단어를 아스키코드로 변환 후 뒤에서 시작하는게 빠른지 앞에서 시작하는게 빠른지 비교
    tb += Math.min(n.charCodeAt() - 65, 91 - n.charCodeAt());
    
    // 2. 좌우 이동
    // 좌우 이동 인덱스(각 단어 위치라고 생각하면 편함. 단, 1부터 시작)
    let idx = i + 1;

    // 연속되는 A의 개수 count
    while (idx < name.length && name[idx] === 'A') idx++;

    lr = Math.min(
      // 그냥 처음부터 끝까지 쭉 비교
      lr,
      // 처음부터 비교하다가 A 뭉텅이를 만나 뒤로 가서 A 뭉텅이 다음 단어부터 비교
      i * 2 + name.length - idx,
      // 처음부터 뒤에서 시작했다가 앞으로 가기
      i + 2 * (name.length - idx),
    );
  });

  return tb + min_move;
}

중간에 헷갈려서 이해하는데 시간 꽤 쏟은 문제.. 문제 자체도 조금 복잡한 것 같다. 한시간 반 이상은 쏟았다.. 장렬하게 전사^^... 

 

+ 다시 한번 복기하는데도 풀이 이해에 시간이 오래걸리는 역대급 문제 ㅋㅋㅋ 

복기

4/10