문제
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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 |
접근
기존에 생각했던 부분 (반례 존재)
A의 존재 여부와 관계 없이 이동은 무조건 오른쪽으로 하여 조이스틱의 움직임을 최소화한 값을 구한다.
A가 있을 경우
-
두 번째 자리에 (인덱스 상으로는 첫 번째 자리에) A가 있을 경우
시작 커서는 무조건 첫 번째에 있다. 두 번째 자리에 A가 있을 경우 뒤로 돌아서 역방향으로 탐색하는 것이 이득이다.
-> 두 번째 자리부터 연속된 A의 개수를 구하고 그만큼 움직인 횟수라고 생각하여 전에 구했던 조이스틱의 움직임을 최소화한 값에서 빼준다. -
마지막 번째 자리에 A가 있을 경우
정방향으로 진행한 다음 A가 시작되는 부분(단, 이 A는 마지막 번째의 문자 A까지 쭉 문자열이 A로 이루어져야 한다.) 이전에 이동을 멈춘다.
-> 마지막 번째 자리부터 역순으로 연속된 A의 개수를 구하고 그만큼 움직인 횟수라고 생각하여 전에 구했던 조이스틱의 움직임을 최소화한 값에서 빼준다.
코드
class Solution {
public int solution(String name) {
int length = name.length();
int cnt = 0;
// 정방향
for (int i = 0; i < length; i++) {
char c = name.charAt(i);
cnt += Math.min(c - 'A', 'Z' - c + 1);
if (i < length - 1) {
cnt++; // 오른쪽으로 이동
}
}
int aCnt1 = 0; // 정방향 탐색 시 마지막 구간에서 중간 특정 지점까지 연속 A 카운터
int aCnt2 = 0; // 역방향 탐색 시 인덱스 상 1번째부터 중간 특정 지점까지 연속 A 카운터
// 정방향에서 사용
if (name.charAt(length - 1) == 'A') {
for (int i = length - 1; i > 0; i--) {
if (name.charAt(i) == 'A') {
aCnt1++;
} else {
break;
}
}
}
// 역방향에서 사용
if (length > 1 && name.charAt(1) == 'A') {
int idx = 1;
while (idx < length && name.charAt(idx) == 'A') {
idx++;
aCnt2++;
}
}
return Math.min(cnt - aCnt1, cnt - aCnt2);
}
}하지만 이 경우, 반례가 존재하였다.
반례
"BBAAAAAAAAC"의 경우, 두 번째 자리에 (인덱스 상으로는 첫 번째 자리에) A가 있는 것도, 마지막 번째에 A가 있는 것도 아니다. 따라서 위의 방식이라면 정방향으로 진행하고 마치게 될 것이다.
하지만, 이동을 최소화하려면 BB에 대해서 조이스틱으로 조작 후 역방향으로 돌아 나와 맨 끝으로 이동하여 C에 대해 조이스틱으로 조작하고 마쳐야 한다.
코드 수정
위의 반례로 보았을 때, A가 연속으로 존재하는 부분이 어디에든 위치할 수도 있고, 여러 번 존재할 수도 있겠다는 생각을 하게 되었다. 따라서 A가 연속으로 있는 부분의 시작 인덱스와 끝 인덱스를 저장하는 리스트를 생성하고 중간에 A를 만나면 돌아 나오도록 하는 방향으로 전략을 수정하였다.
(단, 마지막에 A가 있을 경우, 돌아나오지 않고 중간에서 마치는 것이 이득이므로 예외적으로 처리하였다.)
코드
import java.util.*;
class Solution {
class Node implements Comparable<Node>{
int start;
int end;
Node (int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Node node) {
return node.start - this.start;
}
}
public int solution(String name) {
int length = name.length();
List<Node> aIdx = new ArrayList<>();
for (int i = 0; i < length; i++) {
char c = name.charAt(i);
if (c == 'A') {
int start = i;
i++;
while (i < length && name.charAt(i) == 'A') {
i++;
}
int end = i - 1;
aIdx.add(new Node(start, end));
}
}
int answer = 0;
// 순방향
for (int i = 0; i < length; i++) {
char c = name.charAt(i);
answer += Math.min('Z' - c + 1, c - 'A');
if (i < length - 1) {
answer++;
}
}
for (int i = 0; i < aIdx.size(); i++) {
int cnt = 0;
Node node = aIdx.get(i);
// 첫 부분 정상 진행
for (int j = 0; j < node.start; j++) {
char c = name.charAt(j);
cnt += Math.min('Z' - c + 1, c - 'A');
if (j < node.start - 1) {
cnt++;
}
}
if (node.end == length - 1) {
if (answer > cnt) {
answer = cnt;
}
continue;
}
// 되돌아가기
if (node.start == 0) {
cnt++;
} else {
cnt += node.start;
}
for (int j = length - 1; j > node.end; j--) {
char c = name.charAt(j);
cnt += Math.min('Z' - c + 1, c - 'A');
if (j > node.end + 1) {
cnt++;
}
}
if (answer > cnt) {
answer = cnt;
}
}
return answer;
}
}