문제
문제 설명
게임할 때 이름을 바꾸는 거처럼 조이스틱으로 A로 채워져 있는 기본 문자열을 내가 원하는 name 으로 바꾸는 문제이다.
주의해야 할 점은 커서는 순환되는 구조여서 처음과 끝을 이동할때 역방향으로 이동할 수 도 있다.
첫번째 구현
첫번째로 구한 방식에서 테스트케이스는 통과했는데 코드를 실행해보니 48.1 / 100.0 점수를 받았다.
일단 첫번째로 구현한 방향은 현재 위치에 cursorIndex를 두고 그 때에 이동 비용과 변경 비용을 합한 cost 가 가장 적은 것을 바꾸고 인덱스를 변경하는 방법이였다.
while(!Arrays.equals(current, target)){
int minCost = 50;
int nextIndex = -1;
int moveCost = 0;
int changeCost = 0;
//비용 확인
//비용 = 이동 비용 + 변경비용
for(int i = 0; i < n; i++){
//같으면 넘어가기
if(current[i] == target[i]){
continue;
}
//다르면 비용계산
//이동 비용계산
int move = Math.min(i - cursorIndex, n - (i - cursorIndex));
//변경 비용계산
int change = Math.min((target[i] - current[i] + 26) % 26, (current[i] - target[i] + 26) % 26) ;
int cost = moveCost + changeCost;
if(cost < minCost){
minCost = cost;
nextIndex = i;
moveCost = move;
changeCost = change;
}
}
//최소 비용이 구해지면
current[nextIndex] = target[nextIndex];
cursorIndex = nextIndex;
answer += (moveCost + changeCost);
}두번째 구현
왜 틀렸는지 도저히 모르겠어서 블로그를 참고해보니 연속으로 A 가 있다면 해당 구간을 건너뛰면서 이동을 하는게 좋다고 한다.
그래서 커서 이동을 단순하게 하는게 아니라 A가 많은 구간을 양쪽 방향을 모두 고려하면서 계산해야 한다고 했다.
일단 첫번째로 변경 비용을 한번에 계산한다. 어차피 변경이 될 값들이니 먼저 계산을 해두었다.
// 1. 변경 비용 계산
for (int i = 0; i < len; i++) {
char c = name.charAt(i);
answer += Math.min(c - 'A', 'Z' - c + 1);
}그리고 나서는 이동 거리를 계산한다.
일단 move 라는 변수를 두고 이동하는데 드는 비용을 나중에 초기화 해주긴 하겠지만 최악의 경우인 맨 오른쪽 끝에 갔을 경우인 len - 1로 선언해둔다.
그 후 전체 길이만큼 반복을 하면서 A 가 연속되는 구간을 찾아서 그 구간을 건너뛰는 방법을 찾는다.
현재 루프 변수인 i 의 다음 인덱스를 next로 선언하고 next의 값이 A 면 next를 증가시키면서 건너뛰어준다.
for (int i = 0; i < len; i++) {
int next = i + 1;
// 연속된 A 구간 건너뛰기
while (next < len && name.charAt(next) == 'A') {
next++;
}
//구현
}그리고 나서는 move 변수를 초기화해줘야 한다.
오른쪽을 통해 왼쪽으로 가는 경우와 왼쪽을 통해 오른쪽으로 돌아가는 방법 두가지가 있다.
- 오른쪽을 통해 왼쪽으로 가는 경우
이 때의i는 왼쪽에서 바꿔야 할 마지막 문자 인덱스라고 보고
(i * 2)는 오른쪽으로i까지 가고, 다시 왼쪽으로 돌아오는데i만큼 더 이동한다는 뜻이고
len - next는 연속된A의 다음 위치부터 오른쪽 끝까지 커서를 이동하는 변수이다.
move = Math.min(move, i * 2 + len - next);- 왼쪽을 통해 오른쪽으로 가는 경우
len - next는 오른쪽에서 바꿔야 할 마지막 문자 이후까지 이동하는 경우이다.
(len - next) * 2는 오른쪽 끝까지 갔다가 다시 왼쪽으로 돌아올 이동이고
i는 처음 왼쪽에서 바꾸는 문자까지 커서를 이동하는 방식이다.
move = Math.min(move, (len - next) * 2 + i);예시로 아래와 입력이 아래와 같다고 해보자.
name = "JAZAAAAAAJ"
index: 0 1 2 3 4 5 6 7 8 9
J A Z A A A A A A J지금 가장 길게 연속된 A 를 제외하고는 index 2까지 바꿔야 하고 index 9도 바꿔야 한다.
중간에 A가 많으니깐 0에서 시작된 인덱스를 2까지 갔다가 다시 0 -> 9 로 돌아가는 게 최선인지
아니면 바로 9 먼저 갔다가 돌아와서 2까지 가서 바꾸는게 최선인지를 보는 방법이다.
이렇게 해서 move와 위에서 계산한 answer 를 리턴해주면 된다.
코드
class Solution {
public int solution(String name) {
int answer = 0;
int len = name.length();
// 1. 변경 비용 계산
for (int i = 0; i < len; i++) {
char c = name.charAt(i);
answer += Math.min(c - 'A', 'Z' - c + 1);
}
// 2. 이동 최소 거리 계산
int move = len - 1; // 기본값: 끝까지 오른쪽
for (int i = 0; i < len; i++) {
int next = i + 1;
// 연속된 A 구간 건너뛰기
while (next < len && name.charAt(next) == 'A') {
next++;
}
move = Math.min(move, i * 2 + len - next);
move = Math.min(move, (len - next) * 2 + i);
}
return answer + move;
}
}