다시는 돌아갈 필요가 없다고 가정해서 진행을 했어요. 정방향으로 쭉, 역방향으로 쭉 진행하면 둘 중 작은 수가 답이라 생각했어요. 하지만 이 경우, ABBAAAAABB
처럼 앞에 B
두개를 처리하고 뒤로 돌아가서 B
를 처리하는 부분을 생각 못했어요.
class Solution {
public int solution(String name) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < name.length(); ++i)
sb.append('A');
final int ALPHABET_RANGE = 'Z' - 'A' + 1;
// 정방향
int rot = name.charAt(0) - 'A';
int rotR = ALPHABET_RANGE - rot;
int rotAns = Math.min(rot, rotR);
sb.setCharAt(0, name.charAt(0));
for(int i = 1; i < name.length(); ++i){
if(sb.toString().compareTo(name) == 0)
break;
rotAns++;
rot = name.charAt(i) - 'A';
rotR = ALPHABET_RANGE - rot;
rotAns += Math.min(rot, rotR);
sb.setCharAt(i, name.charAt(i));
}
// 역방향
for(int i = 0; i < name.length(); ++i)
sb.setCharAt(i, 'A');
rot = name.charAt(0) - 'A';
rotR = ALPHABET_RANGE - rot;
int rotRAns = Math.min(rot, rotR);
sb.setCharAt(0, name.charAt(0));
for(int i = name.length() - 1; i > 0; --i){
if(sb.toString().compareTo(name) == 0)
break;
rotRAns++;
rot = name.charAt(i) - 'A';
rotR = ALPHABET_RANGE - rot;
rotRAns += Math.min(rot, rotR);
sb.setCharAt(i, name.charAt(i));
}
return Math.min(rotAns, rotRAns);
}
}
고민 끝에 결국 풀이를 봤어요. 전개한 시점을 기준으로 이대로 진행하는 것이 더 적을지 아니면 돌아가서 진행하는 것이 더 빠를지에 대한 예외처리가 있었어요혼자 푸신분 존경합네다....
// len - next :
// 총 길이에서 현재 바로 다음에 연속된 A가 지나고 남은 문자 갯수
// i : 오른쪽으로의 현재까지의 이동횟수
// i + len - next + i : 현재까지 왔다가 다시 돌아가서 남은 거 까지 가는 이동 횟수
// min(i,len-next)에서,
// i 보다 len-next 값이 작은 경우에 len-next를 선택하는데
// 이는, 마지막 문자가 A인 경우를 제외 하면
// 무조건 len-1 보다 크게 된다 (len-next >=1)
// 따라서,i가 len-next(남은 문자)보다 큰 경우는
// 굳이 왼쪽으로 다시 돌아갈 필요가 없다.
// 대신 끝이 A인 경우는, len-next가 0이 되므로,
// 무조건 len-1 보다 작은 i 가 최소 이동횟수가 된다.
// 따라서 Math.min(i,len-next) 이 부분은 식에서 필요하게 된다.
min_move = Math.min(min_move, Math.min(i+len-next+ Math.min(i,len-next) ));
오 근데 소름 돋네요. 이거 22년 2월 기준 틀렸다고 뜨네요. 보니까,
아직 못 찾은 예외처리가 존재하나 보네요...다시 풀이 실패 해놓고 다시 풀어봐야 겠어요.
class Solution {
public int solution(String name) {
int answer = 0;
// 최대 이동 값은 끝까지 정방향으로 가는 것
int minMove = name.length() - 1;
int length = name.length();
for(int i = 0; i < length; ++i){
answer += getMinValue(name.charAt(i));
int next = i + 1;
while(next < length && name.charAt(next) == 'A')
next++;
minMove = Math.min(minMove, i + i + (length - next));
}
answer += minMove;
return answer;
}
private int getMinValue(char alphabet){
int rot = alphabet - 'A';
int rotR = 'Z' - alphabet + 1;
return Math.min(rot, rotR);
}
}