99클럽 코테 스터디 19일차 TIL / [프로그래머스] 조이스틱

오늘의 학습 키워드

---

그리디

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42860

• 플랫폼: 프로그래머스
• 문제명: 조이스틱
• 난이도: Lv2

풀이

---

import java.util.*;

class Solution {
    
    public int solution(String name) {
        int upDownCnt = 0;
        int leftRightCnt = name.length() - 1;

        for (int i = 0; i < name.length(); i++) {
            upDownCnt += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            
            int indexA = i + 1;
            while(indexA < name.length() && name.charAt(indexA) == 'A') {
                indexA++;
            }
            
            // Math.min(순서대로 진행하는 경우, 뒤로 돌아가는 경우)
            leftRightCnt = Math.min(leftRightCnt, i + i + name.length() - indexA);
            // Math.min(leftRightCnt, 처음부터 뒤로 갔다가 돌아와서 순서대로 진행하는 경우)
            leftRightCnt = Math.min(leftRightCnt, (name.length() - indexA) * 2 + i);
        }

        return upDownCnt + leftRightCnt;
    }
}

접근

• 상하 움직임의 최솟값은 구하기 쉬웠지만, 좌우 움직임의 최솟값은 구하기 어려운 문제였습니다.
• 상하

  upDownCnt += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);

  • 위로 움직임: name.charAt(i) - ‘A’
  • 아래로 움직임: ‘Z’ - name.charAt(i) + 1
• 좌우

  int indexA = i + 1;
  while(indexA < name.length() && name.charAt(indexA) == 'A') {
      indexA++;
  }
  
  // Math.min(순서대로 진행하는 경우, 뒤로 돌아가는 경우)
  leftRightCnt = Math.min(leftRightCnt, i + i + name.length() - indexA);
  // Math.min(leftRightCnt, 처음부터 뒤로 갔다가 돌아와서 순서대로 진행하는 경우)
  leftRightCnt = Math.min(leftRightCnt, (name.length() - indexA) * 2 + i);

  • 좌우 움직임의 경우, 정답이 될 수 있는 3가지 케이스가 존재합니다.
    1. 오른쪽으로 순서대로 진행
       ⇒ 이 경우에는 움직임은 문자열길이 - 1로 고정됩니다.
    2. 오른쪽으로 순서대로 진행하다가 뒤로 돌아가는 경우
    3. 뒤로 갔다가 돌아가서 오른쪽으로 순서대로 진행하는 경우
  • 2, 3번의 경우가 최소 움직임이 되기 위해선 문자열 내에 연속된 A가 존재해야 합니다. (돌아감에도 최소가 되어야 하므로)
  • 따라서, 문자열의 각 위치에서 다음에 존재하는 연속된 A의 인덱스를 계산하여

    int indexA = i + 1;
    while(indexA < name.length() && name.charAt(indexA) == 'A') {
        indexA++;
    }

    • 2번의 경우처럼 이동할 것인지, 3번의 경우처럼 이동할 것인지 최솟값을 따져보면 됩니다.

      // 2. Math.min(순서대로 진행하는 경우, 뒤로 돌아가는 경우)
      leftRightCnt = Math.min(leftRightCnt, i + i + name.length() - indexA);
      // 3. Math.min(leftRightCnt, 처음부터 뒤로 갔다가 돌아와서 순서대로 진행하는 경우)
      leftRightCnt = Math.min(leftRightCnt, (name.length() - indexA) * 2 + i);

소요 시간

3시간