조이스틱 (Programmers Lv.2)

문제

...
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=cpp

프로그래머스

 

풀이

이 문제는 그리디(Greedy)를 이용하여 해결한다. 다만, 문제를 끝끝내 풀지 못해 다시 공부하는 느낌으로 들고 와봤다.

 

처음 풀이)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string start;

pair<int, int> leftCntCheck(int idx, string name) {
    int cnt = 0;
    
    while(start[idx] == name[idx]) {
        idx--;
        cnt++;
        
        if(idx == -1)
            idx = name.length() - 1;
    }
    
    return { idx, cnt };
}

pair<int, int> rightCntCheck(int idx, string name) {
    int cnt = 0;
    
    while(start[idx] == name[idx]) {
        idx++;
        cnt++;
        
        if(idx == name.length())
            idx = 0;
    }
    
    return { idx, cnt };
}

int solution(string name) {
    int answer = 0;
    
    for(int i = 0; i < name.length(); i++) {
        start += 'A';
    }
    
    int idx = 0;
    while(1) {
        answer += min(name[idx] - 'A', 'Z' - name[idx] + 1);
        start[idx] = name[idx];
        
        if(start == name)
            break;
        
        pair<int, int> left = leftCntCheck(idx, name);
        pair<int, int> right = rightCntCheck(idx, name);
        
        if(left.second < right.second) {
            idx = left.first;
            answer += left.second;
        }
        else {
            idx = right.first;
            answer += right.second;
        }
    }
    
    return answer;
}

 

조이스틱의 위아래는 처리하기 쉬우니 패스, 좌우로 이동이 문제인데... 일단 나는 왼쪽으로 이동했을 때 다른 알파벳, 오른쪽으로 이동했을 때 다른 알파벳이 나올 때까지 카운트를 세어 비교하는 방식으로 경로를 찾아가는 풀이법을 택했다.

 

하지만... 이 풀이 방식은 70%정도의 정답률... 나머지는 테케가 나가버린다.

 

대표적인 반례에는 "ABABAAAABA" 가 있는데, 내 풀이로는 오른쪽으로 이동한 후 왼쪽으로 이동한다. 그럼 결과가 11. 그러나 이 반례의 정답은 왼쪽으로 먼저 이동한 후 오른쪽으로 이동하여 10이 된다. 

 

참고 풀이)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string name) {
    int answer = 0;
    
    int cnt = 0;
    int move = name.length() - 1;
    for(int i = 0; i < name.length(); i++) {
        // 위아래
        answer += min(name[i] - 'A', 'Z' - name[i] + 1);        
        
        // 인덱스 체크
        int idx = i + 1;
        while(idx < name.length()) {
            if(name[idx] == 'A')
                idx++;
            else
                break;
        }
        
        // 정방향, 역방향 비교 후 할당
        cnt = name.length() - 1 - idx + 1;
        move = min(move, i + cnt + min(i, cnt));         
    }
    
    return answer + move;
}

 

JS 풀이)

function solution(name) {
    let answer = 0;
    
    let cnt = 0;
    let move = name.length - 1;
    
    for(let i = 0; i < name.length; i++) {
        answer += Math.min(name[i].charCodeAt() - 'A'.charCodeAt(), + 'Z'.charCodeAt() - name[i].charCodeAt() + 1);
        
        let idx = i + 1;
        while(idx < name.length) {
            if(name[idx] === 'A')
                idx++;
            else
                break;
        }
        
        cnt = name.length - 1 - (idx - 1);
        move = Math.min(move, i + cnt + Math.min(i, cnt));
    }
    
    return answer + move;
}

 

알고리즘.... 어렵다....