반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 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 |
문제 접근
이 문제는 그리디 알고리즘을 활용하여 조이스틱 조작 횟수를 최소화하는 문제입니다. 각 위치에서 원하는 문자로 변경하는 데 필요한 최소 횟수와 커서를 움직이는 최적 경로를 계산하여 해결할 수 있습니다.
- 알파벳 변경 비용 계산
- 각 문자에서 'A'로부터 얼마나 떨어져 있는지를 계산하여, 최소 이동 횟수를 구합니다.
- 커서 이동 경로 최적화
- 각 위치에서 커서를 오른쪽이나 왼쪽으로 이동하는 경우 중 최소 이동 횟수를 선택합니다.
- 연속된 '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;
}
}
풀이 설명
- 알파벳 변경 비용 계산
- Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1)를 통해 현재 위치의 문자에서 'A'로부터 변경하는 데 필요한 최소 횟수를 계산합니다.
- 알파벳은 'A'에서 시작하여 'Z'까지 갈 수 있으며, 위로 가는 방법과 아래로 가는 방법 중 더 적은 횟수를 선택합니다.
- 커서 이동 경로 최적화
- move 변수를 통해 커서 이동의 최소 횟수를 추적합니다. 초기값은 커서를 맨 오른쪽 끝까지 이동하는 경우로 설정합니다.
- while 문을 통해 연속된 'A'가 있는 구간을 건너뛰고, 이 구간을 우회하는 방법이 더 효율적인지 확인합니다.
- i * 2 + name.length() - index는 커서를 왼쪽으로 돌아가는 경우, (name.length() - index) * 2 + i는 오른쪽으로 돌아가는 경우를 고려한 이동 횟수입니다.
- 최종 계산
- 알파벳 변경에 필요한 횟수와 최적화된 커서 이동 횟수를 더하여 최종적으로 필요한 최소 조작 횟수를 반환합니다.
마무리하며
- 이번 문제를 통해 그리디 알고리즘을 활용하여 문자열 조작 문제를 효율적으로 해결하는 방법을 배웠습니다.
- 커서 이동의 최적 경로를 계산하는 과정에서 다양한 경우의 수를 고려하여 최소 횟수를 찾는 것으로 문제를 해결했습니다.
반응형
