나의 풀이
테스트 케이스를 모두 만족시키려 수정을 많이 하다보니 코드가 좀 길어진 감이 있다.
상하로 알파벳을 변경하는 최소 횟수와 좌우로 글자 자리를 변경하는 최소 횟수를 따로 나눠서 구했다. 편하게 1번과 2번이라고 지칭하겠다.
코드에 대해서 차근차근 설명해보겠다.
다음은 1번을 구하는 로직이다.
조이스틱을 위로 변경하는 횟수와 아래로 변경하는 횟수 중 최소인 수를 저장한다.
int total_alphabet_number = 0;
for (auto& c : name)
{
total_alphabet_number += min(c - 'A', 'Z' - c + 1);
}그 다음엔 A가 연속으로 나오는 최대 개수(max_a_cnt)와 그 최대 개수를 맞이하기 전 인덱스(cnt_before_max)를 구한다.
int max_a_cnt = 0;
int a_cnt = 0;
int cnt_before_max = 0;
for (size_t i = 1; i < name.size(); i++)
{
if (name[i] == 'A')
{
++a_cnt;
continue;
}
if (max_a_cnt < a_cnt)
{
max_a_cnt = a_cnt;
cnt_before_max = i - max_a_cnt - 1;
}
a_cnt = 0;
}
if (max_a_cnt < a_cnt)
{
max_a_cnt = a_cnt;
cnt_before_max = name.size() - max_a_cnt - 1;
}2번을 구하기 전에 주어진 문자가 전부 A인 경우를 배제시킨다. 이 때 0을 리턴한다.
if (max_a_cnt == name.size() - 1 && name[0]=='A') return 0;다음은 2번을 구하는 첫 번째 방법이다.
문자열 크기에서 뒤에 A가 연속된 경우를 뺀다.
예를 들어 AAABAAAA일 때 오른쪽 방향으로 3칸 움직이면 된다.
그 다음은 문자열 크기에서 앞에 A가 연속된 경우를 뺀다.
예를 들어 AAAAABBA일 때 왼쪽 방향으로 3칸 움직이면 된다.
auto pos = find_if(name.rbegin(), name.rend(), [](char a) {return a != 'A'; });
int behind_a_cnt = distance(name.rbegin(), pos);
auto pos2 = find_if(name.begin(), name.end(), [](char a) {return a != 'A'; });
int front_a_cnt = distance(name.begin(), pos2);
int way1 = min(name.size() - 1 - behind_a_cnt, name.size() - front_a_cnt);문자에 A가 없는 경우는 무조건 첫 번째 방법을 사용하므로 다른 방법을 체크할 필요없이 바로 답을 리턴한다.
if (max_a_cnt == 0)
{
return total_alphabet_number + way1;
}
다음은 2번을 구하는 두 번째 방법이다.
오른쪽 방향으로 이동하다가 문자 중간에 연속으로 A가 가장 많이 나오는 구간을 마주칠 때 왼쪽 방향으로 돌아간다.
예를 들어 BABAAAAAABAB일 때 오른쪽 방향으로 3번째 자리까지 가서 알파벳을 바꾸고 왼쪽으로 계속 이동하면서 알파벳을 바꾼다.
int way2 = cnt_before_max + name.size() - max_a_cnt - 1;다음은 2번을 구하는 세 번째 방법이다.
왼쪽 방향으로 이동하다가 문자 중간에 연속으로 A가 가장 많이 나오는 구간을 마주칠 때 오른쪽 방향으로 돌아간다.
예를 들어 BABAAAAABB일 때 왼쪽 방향으로 끝에서 두 번째 자리까지 가서 알파벳을 바꾸고 오른쪽으로 계속 이동하면서 알파벳을 바꾼다.
int way3 = 2 * name.size() - 2 - 2 * max_a_cnt - cnt_before_max;위의 세가지 방법 중에 최솟값을 리턴한다.
return total_alphabet_number + min(min(way1, way2), way3);🎉완성코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(string name) {
int total_alphabet_number = 0;
for (auto& c : name)
{
total_alphabet_number += min(c - 'A', 'Z' - c + 1);
}
int max_a_cnt = 0;
int a_cnt = 0;
int cnt_before_max = 0;
for (size_t i = 1; i < name.size(); i++)
{
if (name[i] == 'A')
{
++a_cnt;
continue;
}
if (max_a_cnt < a_cnt)
{
max_a_cnt = a_cnt;
cnt_before_max = i - max_a_cnt - 1;
}
a_cnt = 0;
}
if (max_a_cnt < a_cnt)
{
max_a_cnt = a_cnt;
cnt_before_max = name.size() - max_a_cnt - 1;
}
if (max_a_cnt == name.size() - 1 && name[0]=='A') return 0;
auto pos = find_if(name.rbegin(), name.rend(), [](char a) {return a != 'A'; });
int behind_a_cnt = distance(name.rbegin(), pos);
auto pos2 = find_if(name.begin(), name.end(), [](char a) {return a != 'A'; });
int front_a_cnt = distance(name.begin(), pos2);
int way1 = min(name.size() - 1 - behind_a_cnt, name.size() - front_a_cnt);
if (max_a_cnt == 0)
{
return total_alphabet_number + way1;
}
int way2 = cnt_before_max + name.size() - max_a_cnt - 1;
int way3 = 2 * name.size() - 2 - 2 * max_a_cnt - cnt_before_max;
return total_alphabet_number + min(min(way1, way2), way3);
}추천을 많이 받은 풀이
내가 했던 방법에서 복잡한 계산없이 간략하게 짜여져서 감탄했다.
계산없이 알파벳마다 숫자를 정해서 배열에 넣었는데 그렇게까지 할 필요는 없을 것 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int LUT[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1 };
int solution(string name) {
int answer = 0;
for (auto ch : name)
answer += LUT[ch - 'A'];
int len = name.length();
int left_right = len - 1;
for (int i = 0; i < len; ++i) {
int next_i = i + 1;
while (next_i < len && name[next_i] == 'A')
next_i++;
left_right = min(left_right, i + len - next_i + min(i, len - next_i));
}
answer += left_right;
return answer;
}