🖊️ 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42860#
🖊️ 풀이
처음에 그냥 냅다 갖다박아서 오래걸렸던 것 같다.
처음에는 그냥 커서를 옮기면서 answer를 더해줬다.
근데 그러면 너무 왔다갔다 해야 해서 어려움..
내 머리에서 이건 못 푼다 싶었음..
구글링해서 이해했다.....
이렇게 총 10글자가 있다고 할 때,
cur : 현재 바꾸고 있는 커서의 위치
n : name의 총 길이
일단 모든 글자들에 대해서 바꾼다.
그냥 알파벳만 바꾸는걸 먼저 한 다음에 커서 왔다리갔다리를 한 번에 더해줄 거다.
아래 주석 보면 1번은 당연히 직관적으로 이해할 수 있고,
move가 핵심이다.
한 방향으로 S B A A A A A R R M 순으로 탐색할 때가 최소이자 평범한 거니까 n-1으로 초기화한다.
지금 cur == 0이고 S를 바꿈. 그 다음에 탐색 방향을 정하는데,
SB RRM으로 할지,
SB MRR으로 할지,
탐색 방향을 정하도록 하좌
탐색하는 방법은 2가지가 있음
1) SB MRR
cur까지 탐색하고 역방향으로 MMR 탐색하는 방법
-> cur 까지 갔다가(cur), 원점으로 갔다가(cur), 역방향(n)에서 next까지(n - next) 가는 방법
= cur + cur + (n - next)
= 2 * cur + n - next
2) MRR SB
역방향으로 뒤에서 부터 R까지 탐색하고 (n - next), 다시 원점으로 와서(n-next), B까지 탐색(cur)하는 방법
= (n - next) + (n - next) + cur
= 2 * n - 2 * next + cur
얘네 둘 중 저 횟수가 적은 애로 선택하면 된다.
그래서 얘랑 앞서 설정한 기본값과 비교해준다.
이걸 전체 탐색하면서 비교하면 최소로 탐색하는 방법이 나온다.
이렇게 해주면 ~ 된다~
개 어 렯 다 ㅋㅋ
#include <string>
#include <vector>
using namespace std;
int solution(string name) {
int answer = 0;
int n = name.length();
int move = n - 1;
for(int cur = 0 ; cur < n ; cur++) {
// 1번 : 냅다 탐색
answer += min(name[cur] - 'A', 'Z' - name[cur] + 1);
// 2번 : 탐색 방향 정하기
int next = cur + 1;
while(name[next] == 'A' && next <= n - 1)
next++;
move = min(move, min(2 * cur + n - next, 2 * n - 2 * next + cur));
}
answer += move;
return answer;
}