문제

문제 해결 전략

그리디 알고리즘을 이용해서 문제에 접근해야한다는 생각은 당연히 했다. (c++문자열은 오랜만에 써서 한번 정리를 해놔야겠다.) 우선 for문의 인덱스로 왼쪽에서 오른쪽으로 넘어가는 방식으로 하면 좋을 것 같다는 생각을했다. 그리고 각각의 인덱스 안에서 문자열은 주어진 name 문자의 길이만큼인 A로 초기화되어 있는 문자열을 기준으로 위로가는것과 아래로 가는것 두개의 방식중에서 최소로 가는 것을 선택해서 vector에 저장하는 방식으로 문제를 해결하면 될 것같다는 생각을 했다. 마지막에 vector에 저장된 값을 auto를 이용해서 count 해준후 answer에 넣어주면 될것 같다.

코드1

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string name) {
 	int answer = 0; 
	vector<char> nt(name.length(), 'A');
	answer = name.length()-1;

	for(int i = 0;i < name.length();i++){
		answer += min(name[i]-nt[i], 'Z'-name[i]+1);
	}
    for(auto a:name) if(a == 'A') answer--;
	
	return answer;
}

우선 첫번째 시도치고 나쁘지 않은 성능이었다. 왜냐하면 정확성이 54.5가 나왔기 때문이다 그래서 여기서 내가 무엇을 잘못했는지 고민해보니까, 빼먹은 경우가 있다. SAAZA 이런 경우에는 커서를 굳이 오른쪽으로 세번 이동시켜서 Z에 도달하는 것보다 왼쪽으로 한번 이동하는게 커서이동이 최소화 되기때문에 커서를 왼쪽으로 한번 이동시켜서 연산해보면 S는 'Z'-'S'+1값이 더 작으므로 8번의 커서이동을 하고 Z는 위로 한 번만 이동하면 되기 때문에 총 커서는 왼쪽 2번 위로 9번 총 11회 이동횟수를 가지게 된다.

코드2

//최종 코드
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int solution(string name)
{
	int answer = 0, i = 0;
	int len = name.length(), mid = len / 2;
	int front = 0, back = 0;
	int half_f = 0, half_b = 0;

	answer = name[0] - 'A';
	if (answer > 13)
		answer = 'Z' - name[0] + 1;
	for (int i = 1; i < name.length(); i++)
	{
		if (name[i] <= 'N')
			answer += name[i] - 'A';
		else
			answer += 'Z' - name[i] + 1;
		if (name[i] != 'A')
		{
			front = i;
			if (i <= mid) half_f = i;
		}
		if (name[len - i] != 'A')
		{
			back = i;
			if (len - i > mid) half_b = i;
		}
	}
	answer += min(min(front, back), min(half_b * 2 + half_f, half_f * 2 + half_b));

	return answer;
}

정리를 해보면, A~N까지는 위-방향키로 이동 (0~13), Z~M은 아래-방향키로 (1~12)로 최소 횟수로 변경할 수 있다. 총이동 횟수 변수인 answer에 모든 횟수를 더한다.
초기에는 모든 알파벳을 A로 설정시켜놓기 때문에 A를 바꿀 필요가 없다. 따라서 조이스틱을 최소횟수로 이동시키기 위해서 네가지를 고려해야 한다.

1. 왼쪽 / 뒷부분이 A인 경우 최소
   ex) BBBCEDAA
2. 앞부분이 A인 경우 최소
   ex) AAAEDRT
3. 오른쪽+왼쪽/ 중간에 A가 많은 경우 중 앞 부분에 A가 아닌 알파벳이 더 적은 경우
   ex) CCCAAAAAADSDSDER
4. 왼쪽+오른쪽 / 중간에 A가 많은 경우 중 뒷부분에 A가 아닌 알파벳이 더 적은 경우
   ex) DERWGKLAAAAAAEEE

총 네가지 경우의 수를 고려해서 각각의 이동에 따라 최소값을 계산하게 조건문으로 나누어 주었다.