AAAA... 로 초기화된 상태에서 내가 원하는 닉네임을 만드는데 최소한의 움직임을 구하는 문제이다.
해당 문제를 편하게 분해하자면,
1. 왼쪽 오른쪽으로 이동
2. 위 아래를 이용하여 문자 이동
두 개의 과정으로 나눌 수 있다.
위/아래를 이용하여 문자를 이동하는 것은 문자열이 주어진다면 고정값이 된다.
왼쪽 혹은 오른쪽으로 이동하는 것은 여러가지 이동 방법이 정해져 있지만(왼쪽 or 오른쪽 등)
문자를 이동하는 것은 더욱 짧은 것이 확실히 정해져있기 때문이다.
처음에는 모든 경우의 수를 탐색해볼까라는 생각을 가져봤는데, 시간 초과로 인하여 문제가 해결되지 않았다.
다음번에는 크게 다섯가지 경우를 기반으로 계산하는 방법을 사용했는데, 다음과 같다.
* 움직이지 않음
* 왼쪽으로만 이동
* 오른쪽으로만 이동
* 왼쪽으로 이동하다 오른쪽으로 이동
* 오른쪽으로 이동하다 왼쪽으로 이동
위의 경우를 탐색하는 과정을 소스코드로 옮기면 답을 찾을 수 있는 알고리즘이 완성된다.
자세한 설명은 아래 소스코드의 주석을 활용하였다.
using System;
public class Solution {
/* len, str : 접근용이성을 위하여 class 변수 선언 */
int len;
string str;
public int solution(string name) {
/* count는 먼저, 알파벳의 이동(고정값)을 저장하는 변수
min은 반환 될 최소값 입니다. */
int count = 0;
int min = 0;
/* class 변수 초기화 */
str = name;
len = name.Length;
// 우선 바꿔야 할 알파벳 순서 미리 계산
// -> 해당 하는 순서는 문자열에 대하여 고정적이다.
foreach(char c in name)
count += getCharMove(c);
// count가 0이라는 것은 모든 문자가 'A'로 이루어졌으며 굳이 이동할 필요가 없음을 의미한다.
if(count == 0) return 0;
/*아래 주석처리된 소스코드는 생략 가능하나 이해를 위해 남겨놓음.
- 오른쪽으로만 갈 때
min = getRightMove(0) + count;
- 왼쪽으로만 갈 때
int temp = getLeftMove(0) + count;
min = min<temp ? min : temp;*/
min = 999;
int temp = 0;
for(int i=0; i<len; i++){
// R to L
// 오른쪽으로 i만큼 이동한 뒤 해당 위치에서 왼쪽으로 가는 경우
temp = i + getLeftMove(i) + count;
min = min<temp ? min : temp;
// L to R
// 왼쪽으로 i만큼 이동한 뒤 해당 위치에서 오른쪽으로 가는 경우,
// 왼쪽으로 i만큼 이동하였으니 시작 위치로 len-i를 전달
temp = i + getRightMove(len-i) + count;
min = min<temp ? min : temp;
}
return min;
}
int getRightMove(int start){
//오른쪽으로 갈 경우 오른쪽으로 가야하는 최대 거리를 찾아서 더함.
//한칸씩 왼쪽으로 탐색하여 'A'가 아닌 문자를 찾을 때 까지.
int cur = start-1 > -1 ? start-1 : len-1; // 언더플로우 처리, 음수가 될 경우 최대값을 취해야함.
int loop = len-1; //시작변수로 부터 len-1번 반복
int moves = len-1; //기본적으로 len-1번 이동한다. 'A'를 만날 때 마다 해당하는 문자는 바꿀 필요가 없어 -1해준다.
for(int j=0; j<loop; j++){
if(str[cur] != 'A'){
//만약 맨 첫 loop에서 아래 return을 취한다면, 다른 모든 문자들이 'A'가 아닌경우.
return moves;
}
else{
// 만약 'A'를 만날경우 해당 문자는 안바꿔도 되므로 이동할 수고가 없다.
// 따라서 이동 횟수 -1
moves--;
cur = cur-1 > -1 ? cur-1 : len-1;
}
}
// 시작 문자를 제외하고 다른 문자들이 모두 'A'일 경우
// 굳이 이동할 필요가 없어 return 0
return 0;
}
int getLeftMove(int start){
//왼쪽으로 갈 경우 왼쪽으로 가야하는 최대 거리를 찾아서 더함.
//한칸씩 오른쪽으로 탐색하여 'A'가 아닌 문자를 찾을 때 까지.
int cur = start+1 >= len ? 0 : start+1;
int loop = len-1;
int moves = len-1;
for(int j=0; j<loop; j++){
if(str[cur] != 'A'){
return moves;
}
else{
moves--;
cur = cur+1 >= len ? 0 : cur+1;
}
}
// 시작 문자를 제외하고 다른 문자들이 모두 'A'일 경우
// 굳이 이동할 필요가 없어 return 0
return 0;
}
// 해당 문자를 만들기 위하여 필요한 이동 수를 반환하는 getCharMove 메서드.
// 알파벳은 'N'을 기점으로 위로 이동하는게 더 빠를지 밑으로 이동할게 더 빠를지
// 분기된다. 'N'은 어느쪽으로 하여도 13번의 이동이 필요하다.
int getCharMove(char c){
if(c > 'N') return 'Z'-c+1;
else return c-'A';
}
}
