프로그래머스 - 조이스틱 & BOJ - 고득점 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42860

https://www.acmicpc.net/problem/3663

3663번: 고득점

코딩테스트 연습 - 조이스틱

 

 

문제 풀이

"AAA..."에서 만들고자 하는 문자열로 바꾸려면 2가지 단계를 거쳐야 한다.

1. 알파벳 변경 조작 횟수를 센다.

2. 커서 변경 조작 횟수를 센다.

 

1의 경우, A에서 변경하는 것이므로 미리 배열을 생성할 수 있다. 예를 들어 A = 0, B = 1, C = 2, ...이고 N = 13 부터는 뒤에서부터 세는 것이 빠르기 때문에 12, 11, ..로 줄어들어 Z = 1이다. (A에서 아래로 한 번만 가면 Z이므로)

 

2의 경우, 다시 3가지 경우로 나눌 수 있다.

• 한 쪽 방향으로만 세는 것이 제일 미니멈인 경우 ex) JEROEN
  이 경우는 커서를 문자열의 크기만큼 이동해야 하므로 name.size() - 1이 된다.
• 오른쪽으로 커서를 옮기다가 왼쪽으로 방향을 바꾸는 것이 제일 미니멈인 경우 ex) ABAAAABABA
  즉, 연속된 A의 왼쪽을 2번 세고 오른쪽을 1번 센다. (다시 돌아오기 때문)
• 왼쪽으로 커서를 옮기다가 오른쪽으로 방향을 바꾸는 것이 제일 미니멈인 경우 ex) ABABAAAABA
  즉, 연속된 A의 왼쪽을 1번 세고 오른쪽을 2번 센다.

임시 변수 tmp에 인덱스를 저장하고 인덱스마다 연속된 A를 세어 그 만큼 tmp를 증가시켜준다.
이를 이용하여 연속된 A의 왼쪽 문자열 크기 left, 오른쪽 문자열 크기 right를 구한다.
left는 해당 인덱스 - 1 (다음부터는 A가 나오므로)
right는 문자열의 크기 - tmp (tmp 변수에는 인덱스 + 연속된 A가 있으므로)

 

따라서, 커서 변경 조작 횟수는 left + right + min(left+right) 중에서 가장 미니멈인 것을 선택하면 된다.

1과 2를 모두 answer에 더해주면 정답이 된다.

 

쉽게 이해가 되지 않는다면 코드와 함께 ABAAAABABA의 예를 살펴보자.

i = 2일 때 연속된 A가 최대이므로 tmp = 2 + 4(연속된 A의 수)이다. 

이 때, 
left = i - 1 = 1(AB 중에서 0번째 인덱스 제외)
right = 10 - 6 = 4(BABA)이다.

실제로 오른쪽으로 1번 이동 후 다시 왼쪽으로 1번 이동하는 것이 left를 2번 세는 것이고

나머지 왼쪽으로 4번 이동하는 것이 right를 한 번 세주는 것이다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int alphabetNum[26] = { 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;
    int shift = name.size() - 1; //커서를 한 방향으로만 이동
    
    for(int i=0; i<name.size(); i++){
        //알파벳 변경 조작 횟수
        int tmp = int(name[i]-'A');
        answer += alphabetNum[tmp];
        
        //커서 변경 조작 횟수
        if(i==0) continue;
        if(name[i] == 'A') {
            tmp = i;
            while(tmp < name.size() && name[tmp] == 'A') tmp++;
            
            int left = i - 1;
            int right = name.size() - tmp;
            shift = min(shift, left + right + min(left, right));
        }
    }
    
    answer += shift;
    
    return answer;
}