[프로그래머스] 조이스틱 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

이전에 풀었던 문제인데, 문제 풀이 방법도 생각 안 났고, 기존에 작성했던 코드로는 통과가 안됐다.

지문 수정 및 테스트 케이스 변경이 있었다고 한다.

 

그렇다고 한다.

 

문제

풀이

계산해야하는 정보는 2가지이다.

1. 알파벳을 A에서 목적 알파벳까지 바꾸는데 필요한 횟수

2. 좌우 커서를 이용해 바꿀 필요가 있는 알파벳위치까지 이동하는데 필요한 횟수

 

1. 의 경우는 간단하게 구할 수 있다.

for(int i=0; i<name.size(); i++){
        answer+= min('Z'-name[i]+1, name[i]-'A');
}

 

2.를 구하는 것이 이 문제의 핵심이었는데,

위에서 언급했듯 그리디라면 현재 위치 now 에서 가장 가까운 거리에 있는 'A' 가 아닌 문자로 이동한다. 

해당 문자를 변경하고 또 다시 해당 위치 기준 가까운 'A'가 아닌 문자위치까지 이동한다. -> 반복

 

이런식이어야 하는데 테스트케이스 통과가 안됐다.

계속 고민해봐도 도무지 방법이 안 떠올라서 질문하기에 있는 팁을 참고했다.

 

 

발생할 수 있는 경우는 다음 4가지이다.

1. 오른쪽으로 쭉 이동

2. 왼쪽으로 쭉 이동

3. 오른쪽으로 갔다가 특정 위치에서 왼쪽으로 이동

4. 왼쪽으로 갔다가 특정 위치에서 오른쪽으로 이동

 

만약 주어진 문자열에 A로만 이루어진 구간이 존재한다면, 그 구간들 중 한 구간을 생략할 수 있다. ->3,4번이 해당 케이스를 계산하는 것

 

예를들어 BAAABBBAAB 라는 문자열이 존재한다면, 문자열에 존재하는 A로만 이루어진 구간은 총 두개이다 AAA, AA

이 둘 중 하나만 생략할 수 있다. 모든 A가 아닌 지점을 방문해야하기 때문(조금만 생각해보면 직관적으로 알 수 있다.) 

가장 적합한 것은 그 구간들중 가장 긴 구간을 생략하는 것이다.

 

나는 'A'가 아닌 것들의 index를 vector<int> idx에 저장한 후에

사이값이 가장 큰 경우의 왼쪽값과 오른쪽값을 각각 lf, rg에 저장했다.

그리고 마지막에 다음과 같은 식으로 case 1, 2, 3, 4중 가장 작은 값을 answer에 더해줌으로써 문제를 풀었다.

int tmp1, tmp2;
if(idx.size()>0) tmp1 = min(idx.back()-1, size-idx.front()+1);
tmp2 = min((lf-1)*2 + (size-rg+1), (size-rg+1)*2 + (lf-1));
answer+=min(tmp1, tmp2);

코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;

int solution(string name) {
    int answer = 0, now = 1, size = name.size();
    vector<int> idx;
    
    for(int i=0; i<name.size(); i++){
        answer+= min('Z'-name[i]+1, name[i]-'A');
        if(name[i]!='A') idx.push_back(i+1);
    }
    
    int before = 1, len, maxLen = 0, lf=size, rg=0;
    for(int i=0; i<idx.size(); i++){
        len = idx[i]-before-1; 
        if(maxLen<len){
            maxLen = len;
            rg = idx[i];
            lf = before;
        }
        before = idx[i];
    }
    int tmp1, tmp2;
    if(idx.size()>0) tmp1 = min(idx.back()-1, size-idx.front()+1);
    tmp2 = min((lf-1)*2 + (size-rg+1), (size-rg+1)*2 + (lf-1));
    answer+=min(tmp1, tmp2);
    
    return answer;
}

 

좌우로 한 칸씩만 이동가능할 때 어떻게 하면 최소횟수를 구할 수 있는지에 대한 알고리즘을 배울 수 있었던 문제였다.

dfs로도 풀이가 가능하다는데, 그럴것 같다.