99클럽 코테 스터디 19일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

문제 & 키워드

• 프로그래머스 - 조이스틱 (문제 링크)
• 그리디 알고리즘
• 문자열 조작
• 최소 이동

---

문제 설명

조이스틱으로 알파벳 이름을 완성해야 합니다. 처음에는 모든 위치가 'A'로 설정되어 있으며, 각 위치를 원하는 문자로 바꿔야 합니다.

조이스틱을 조작하는 방법은 다음과 같습니다:

• ▲ : 다음 알파벳 (A에서 Z로, B에서 A로)
• ▼ : 이전 알파벳 (A에서 Z로, Z에서 A로)
• ◀ : 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자로 이동)
• ▶ : 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자로 이동)

예를 들어 "JAZ"라는 이름을 만들기 위해서는 다음과 같이 조작할 수 있습니다:

• 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 'J'를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 'Z'를 완성합니다.

따라서 "JAZ"를 만들기 위해 11번의 조작이 필요하며, 이 방법이 최소 이동입니다.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

name	return
JEROEN	56
JAN	23

---

문제 접근

이 문제는 그리디 알고리즘을 활용하여 조이스틱 조작 횟수를 최소화하는 문제입니다. 각 위치에서 원하는 문자로 변경하는 데 필요한 최소 횟수와 커서를 움직이는 최적 경로를 계산하여 해결할 수 있습니다.

1. 알파벳 변경 비용 계산
   • 각 문자에서 'A'로부터 얼마나 떨어져 있는지를 계산하여, 최소 이동 횟수를 구합니다.
2. 커서 이동 경로 최적화
   • 각 위치에서 커서를 오른쪽이나 왼쪽으로 이동하는 경우 중 최소 이동 횟수를 선택합니다.
   • 연속된 'A'가 있을 경우, 이를 우회하는 경로가 더 효율적일 수 있으므로, 이러한 상황을 고려하여 이동 경로를 최적화합니다.

 

풀이

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int index;
        int move = name.length() - 1;

        for (int i = 0; i < name.length(); i++) {
            // 알파벳 변경 최소 횟수 계산
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);

            // 연속된 'A'를 피하기 위한 커서 이동 최소화
            index = i + 1;
            while (index < name.length() && name.charAt(index) == 'A') {
                index++;
            }
            move = Math.min(move, i * 2 + name.length() - index);
            move = Math.min(move, (name.length() - index) * 2 + i);
        }
        return answer + move;
    }
}

풀이 설명

1. 알파벳 변경 비용 계산
   • Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1)를 통해 현재 위치의 문자에서 'A'로부터 변경하는 데 필요한 최소 횟수를 계산합니다.
   • 알파벳은 'A'에서 시작하여 'Z'까지 갈 수 있으며, 위로 가는 방법과 아래로 가는 방법 중 더 적은 횟수를 선택합니다.
2. 커서 이동 경로 최적화
   • move 변수를 통해 커서 이동의 최소 횟수를 추적합니다. 초기값은 커서를 맨 오른쪽 끝까지 이동하는 경우로 설정합니다.
   • while 문을 통해 연속된 'A'가 있는 구간을 건너뛰고, 이 구간을 우회하는 방법이 더 효율적인지 확인합니다.
   • i * 2 + name.length() - index는 커서를 왼쪽으로 돌아가는 경우, (name.length() - index) * 2 + i는 오른쪽으로 돌아가는 경우를 고려한 이동 횟수입니다.
3. 최종 계산
   • 알파벳 변경에 필요한 횟수와 최적화된 커서 이동 횟수를 더하여 최종적으로 필요한 최소 조작 횟수를 반환합니다.

 

---

 

마무리하며

• 이번 문제를 통해 그리디 알고리즘을 활용하여 문자열 조작 문제를 효율적으로 해결하는 방법을 배웠습니다.
• 커서 이동의 최적 경로를 계산하는 과정에서 다양한 경우의 수를 고려하여 최소 횟수를 찾는 것으로 문제를 해결했습니다.