문제
https://school.programmers.co.kr/learn/courses/30/lessons/42860
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
분류
그리디(Greedy)
해결
이 문제를 처음 읽었을 땐 까다롭다고 생각하지 못했다. 커서를 왼쪽 오른쪽으로 이동한다 라는 부분을 이미 입력한 문자열에서 고른다고 잘못 생각했기 때문이다.... 답이 틀리게 나와 더 들여다보고 나서야 현재 AAA로 이루어진 문자열에서 이동한다는 말임을 깨달았다.
우선 다음, 이전 알파벳으로 이동하는 것부터 풀어보자 이 부분은 어렵지 않았다. 아스키코드로 바꾸어 계산해주면 금방 구할 수 있다.
for (int i = 0; i < name.length(); i++) {
int cnt = min(name[i] - 'A', 'Z' - name[i] + 1);
answer += cnt;
}A부터 위로 올라가며 탐색하는 것과 Z부터 아래로 내려가며 탐색하는 것중에 더 작은 값을 찾아 저장하면 된다. 각각의 탐색 횟수를 구해 answer에 모두 더해준다.
이제 왼쪽 오른쪽 이동 부분을 계산해준다. 일단 이것은 기본적으로 문자열의 전체 길이에서 1을 뺀 횟수이다. 단 고려해야할 부분이 있는데 문자 A의 경우 기본값이 A로 이미 설정되어 있으므로 굳이 방문하지 않아도 되는 경우가 생긴다는 점이다. 예를 들어 길이가 5인 "BBBAA" 다음 문자열이 주어질 경우 세번째 B까지 두 번만 이동하면 되므로 이동 횟수는 2가된다. 4번째 5번째 A에는 방문하지 않아도 되는 것이다. 또한 "BAAAAABB"와 같은 문자열을 만들 경우 '1번째 B 조작 -> 맨 뒤로 감 -> 뒤의 2개의 B 조작 -> 탐색 종료' 이러한 과정이 최소 이동 횟수가 된다. 이렇게 A로 이루어진 부분 문자열이 있는 경우의 이동 횟수를 구하기 위해 다음과 같은 설계를 했다.
- A로 이루어진 최대 길이 부분 문자열의 시작 인덱스, 끝 인덱스를 저장한다.
- 이 부분 문자열을 기준으로 남은 문자열의 왼쪽 부분과 오른쪽 부분의 길이를 구한다.
- 다음 세 가지 경우중 최솟값이 이동 횟수가 된다
3-1. 왼쪽 남은 문자열을 탐색하고 뒤로 이동하여 끝에서부터 오른쪽 남은 문자열 탐색
3-2. 오른쪽 남은 문자열을 먼저 탐색하고 다시 처음으로 이동하여 왼쪽 남은 문자열 탐색
3-3. 단방향 탐색
int max_len = 0;
int len = 0;
int st = -1;
int start = -100;
int end = -100;
for (int i = 0; i < name.length(); i++) {
if (name[i] == 'A') {
if (len == 0) st = i;
len++;
if (len > max_len) {
start = st;
if (st != 0) start--;
end = i;
max_len = len;
}
}
else len = 0;
}
int move = name.length() - 1;
int right = move - end;
int move_lr = start < right ? start * 2 + right : start + right * 2;
move = min(move, move_lr);
answer += move;반례
처음에는 가장 긴 A 부분 문자열만 구해서 이동 횟수를 구하였는데 이 코드는 반례가 있었다. 바로 "AAABBAAAAABB"와 같이 가장 긴 문자열을 방문하지 않는 것이 아닌, 다른 부분 문자열(이 예시의 경우 첫번째)을 방문하지 않는 것이 이동 횟수가 가장 짧은 경우이다. 그래서 A 부분 문자열을 마주칠 때마다 이동 횟수의 최소값을 구하도록 코드를 수정하였다.
int move = name.length() - 1;
for (int i = 0; i < name.length(); i++) {
if (name[i] == 'A') {
if (len == 0) st = i;
len++;
}
else if (len > 0){
if (st != 0) st--;
end = i - 1;
int right = name.length() - end - 1;
int move_lr = min(st * 2 + right, st + right * 2);
move = min(move, move_lr);
len = 0;
}그러나 이 코드도 테스트를 통과하지 못했다.... 디버깅을 통해 코드를 탐색하니 문자열의 마지막에 A 부분 문자열이 있는 경우 (EX. "BBAAA") 해당 문자열에 대해 이동 횟수를 구하지 않고 반복문이 종료되고 있었다. 맨 마지막 문자 A인 경우 이동 횟수를 구하도록 로직을 추가하였더니 이번엔 통과되었다.
