문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 “JAZ”를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
| name |
return |
| “JEROEN” |
56 |
| “JAN” |
23 |
풀이
원하는 값을 얻기위해선
- 그리디 알고리즘에 기초하여 현재 위치에서의 최적의 수를 계산해야 한다.
- 배열의 첫 인덱스 에서 마지막 인덱스로 이동이 가능하므로 해당 기능을 구현하여 최적의 수를 계산해야 한다.
- 조이스틱의 위, 아래 이동은
char 자료형의 성질을 이용하여 쉽게 계산이 가능하다.
"BABAAAAB" 에서의 최적의 수를 예로 들어보겠다.
숫자는 name의 각 문자의 자리(인덱스) 이며 @는 현재 커서의 위치이다.
행동 하나하나 순서대로 나타내면 아래와 같다.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| @ |
|
|
|
|
|
|
|
| B |
A |
B |
A |
A |
A |
A |
B |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| @ |
|
|
|
|
|
|
|
| A |
A |
B |
A |
A |
A |
A |
B |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| |
|
|
|
|
|
|
@ |
| A |
A |
B |
A |
A |
A |
A |
B |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| |
|
|
|
|
|
|
@ |
| A |
A |
B |
A |
A |
A |
A |
A |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| @ |
|
|
|
|
|
|
|
| A |
A |
B |
A |
A |
A |
A |
A |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| |
@ |
|
|
|
|
|
|
| A |
A |
B |
A |
A |
A |
A |
A |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| |
|
@ |
|
|
|
|
|
| A |
A |
B |
A |
A |
A |
A |
A |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| |
|
@ |
|
|
|
|
|
| A |
A |
A |
A |
A |
A |
A |
A |
이처럼 처음 시작 상태를 제외하고 총 7번의 행동으로 최적의 수를 얻을 수 있었다.
이를 계산하는 방법은 현재 커서의 위치마다 최적의 방향(왼쪽 or 오른쪽)인 기회비용 값이 적은 쪽을 선택하면 된다. 주의할 점은 인덱스 처음과 끝이 연결된 점인데, 파이썬의 경우 배열의 마지막 인덱스를 [-1] 과 같이 쉽게 인덱싱이 가능하지만… 자바는 그렇지 않고 간단히 배열의 길이 - 1 값으로 인덱싱을 해주어야 한다.
만약 어떤 상태에서 위와 같이 S -> G 로 도달하는 것이 목표라면 커서를 왼쪽으로 세번 옮기는 것이 최적의 수일 것이다. 이때 이동거리(3)는 아래와 같이 얻을 수 있다.
배열의 길이(8) - G 위치(6) + S 위치(1)
이러한 규칙들을 발견하는 것이 중요한 것 같다.
따라서 간단한 그리디 알고리즘을 구현하면 쉽게 문제 해결이 가능하다.
코드(Java)
class Greedy_02_Solution {
public int solution(String name) {
int answer = 0;
char[] arr = name.toCharArray();
ArrayList<Integer> idx_list = new ArrayList<Integer>();
// 변경 해야 하는 인덱스의 번호를 리스트에 저장
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 'A') {
idx_list.add(i);
}
}
int idx = 0; // 현재 커서가 가리키는 위치 값
while (!idx_list.isEmpty() && idx >= 0) {
if (arr[idx] != 'A') {
// ASCII 형태의 알파벳 연산
answer += (arr[idx] - 'A' < 'Z' - arr[idx] + 1)
? arr[idx] - 'A'
: 'Z' - arr[idx] + 1;
idx_list.remove(idx_list.indexOf(idx));
}
if (idx_list.isEmpty()) {
break;
}
// 조이스틱 왼쪽, 오른쪽 각각의 최소 이동거리 값 계산
int left_diff = (idx_list.get(idx_list.size() - 1) < idx)
? idx - idx_list.get(idx_list.size() - 1)
: arr.length - idx_list.get(idx_list.size() - 1) + idx;
int right_diff = (idx_list.get(0) > idx)
? idx_list.get(0) - idx
: arr.length - idx + idx_list.get(0);
// 최적의 방향으로 이동 결정
if (left_diff < right_diff) {
idx = idx_list.get(idx_list.size() - 1);
answer += left_diff;
} else {
idx = idx_list.get(0);
answer += right_diff;
}
}
return answer;
}
}
댓글남기기