(✨✨✨✨✨ 별이 다섯개)조이스틱

욥·2026년 3월 27일

프로그래머스_알고리즘

목록 보기

39/90

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    
    
    // 유턴했을 때가 최고의 dist 나올 수 있다. 
    
    // ababaaaaaaabaaaaaaaaaaa
    
    // ababaaaaaaabaa
    
    // aaaaaaabab
    
    // abababaaaaaa
    // 그냥 오른쪽으로 가는게 좋은 경우 
    
    //      x               y
    // abababaaaaaaaaaaaaaaaba
    
    // 첫번재 b발견시 : 2번째 b로 가는 최소 값은 3이다.
    // 2번째 b 발견시 : 3번째 b로 가는 최소값은 3이다.
    // 3번째 b발견시  : 4번째 b로 가는 최소값은 8이다.
    
    // 그럼 내 생각에는 전부 더해야 하는 걸까? 
    // 굳이 누적을 해야 할까? 
    
    // 어차피 3번째 b로 가는 방법은 idx 로 오른쪽 이동, 다시 왼쪽으로 idx 이동 이후에
    // 끝으로 가는 방법이다. 
    
    // => 일단 누적을 하지 않음. 
    
        
    // 쉽게 진행하자.
    
    // 0123456789 101112
    // aabaaaaaaa  b a a : size : 13
    
    // 1번. 그냥 오른쪽으로 쭉 가기 
    // 2번. 유턴하기 
    // 아니면 이런것도 있다.
    // 뒤를 먼저 갔다가 앞으로 진행.
    
    
    // 10 (idx + diff) vs 2 + 2 + size() - 1 - 10 + 1
    // 8 vs 4 + 2 + 1
    
    // 8 vs 4 + 1
    
    //////////// 아래 걸로 증명 됨.
    
    
    // 0123456789 10 11 12 13 14 15
    // aaaabaaaaa  a a  a  a  b  b 
    // 전체 사이즈는 16
    
    // 오른쪽으로 쭉 이동하는 거는 안된다.
    
    // 오른쪽으로 갔다가 다시 u턴하기 
    // 쭉 오른쪽으로 가기 
    
    // 그냥 왼쪽으로 갔다가 다시 원점 지나서 오는거는?
    
    // 오른쪽 가는 거를 x라고 하고 ,
    // 왼쪽으로 가는 거를 y라고 하면 
    
    // 가) 4 + 4 + 16 - 14
    // 나) (16 -14) * 2 + 4
    
    // idx * 2 + size() - nextIdx 
    // ( size() - nextIdx) * 2 + idx;
    
    // 4번에서 14번으로 가는 방법
    
    // 14번에서 15번으로 가는 방법
    // 2개 중에서 매순간 최소값을 선택하기만 하면 된다. 
    
    // 왜냐하면 가번을 통해서 이미 오른쪽으로 가는 방법을 통해서 해결된다. 누적할 필요 없다
    
    int minValue = name.size() - 1;
    
    int ssize = name.size();
    for(int i = 0; i < name.size(); ++i)
    {
        
        // 상하로 이동하는 것만 처리하자. 
        int up = name[i] - 'A';
        int down = 'Z' - name[i] + 1;
        
        answer += min(up, down);
            
        int nextIdx = i + 1;
        
        while(nextIdx < ssize &&  name[nextIdx] == 'A')
        {
            nextIdx++;
        }
        
        // idx * 2 + size() - nextIdx 
        // ( size() - nextIdx) * 2 + idx;
        
        int right = i * 2 + ssize - nextIdx;
        int left = (ssize - nextIdx) * 2 + i;
        
        minValue = min(minValue, min(right, left));
        
    }
    answer += minValue;
    
    
    return answer;
}

아이디어가 중요하다...

https://4z7l.github.io/2021/03/12/algorithms-prg-42860.html

생각해보기

오른쪽으로 쭉 가기
오른쪽으로 쭉 가다가 원점으로 가서 왼쪽으로
왼쪽으로 갔다가 다시 원점으로 와서 오른쪽으로 진행?

누적에 대해서

아래의 주석 내용을 보면, 누적을 할 필요가 없다.
방정식
: 타겟 idx + 타겟 idx + size() - 1 - 발견된 idx + 1(원점에서 꼬리로 가는 카운팅) 을 하면 된다.

오른쪽으로 쭉 가는 방법은 할 필요 없다.

반례

복귀를 해야 하고,
나를 대상으로 뒤에 오는 value 중에 'a'가 아닌 값을 대상으로 확인하는 식으로 하면 이전에 오는 알파벳에 대해 생각할 필요 없다.
-> 이미 완료된 상태다.
2번째 나오는 b로 이동을 한다고 하자. 그러면 굳이 1번째 나오는 b의 왼쪽, 오른쪽 이동에 대해서 생각할 필요 없다.