[프로그래머스] 조이스틱

문제

 

풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int sol1(char c, string al){ 
    int val = 0;
    int p2 = find(al.begin(), al.end(),c) - al.begin();
    if(p2 > al.size()/2){
        p2 = al.size() - p2;
    }
    return p2;
}


int solution(string name) {
    int answer = 0;
    int idx, move = 0;
    int l_len = 0, r_len = 0;
    string al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // 1. 가장 긴 A len 구하기
    move = name.size() -1; // 정방향
    for(int i=0; i<name.size(); i++){
        idx = i+1;
        while(name[idx] == 'A'){
            idx++;
        }
        l_len = i; 
        r_len = name.size() - idx;
        move = min(move, l_len *2 + r_len ); // 정방향 -> 반대
        move = min(move, r_len *2 + l_len ); // 반대 -> 정방향
    }
    

    //4. 세로이동방향 구하기
    for(auto c : name){
        move += sol1(c, al);
    } 
    
    return move;
}

시행착오를 정말 많이 겪은 문제다!

조이스틱의 알파벳들의 끝과 끝이 원처럼 서로 연결되어 있다고 생각하며 알고리즘을 어떻게 짜야할지 고민을 많이 했다.

많은 문서를 참고한 후 결국 문제를 해결할 수 있었다.

 

연속된 A를 구한 후 그것을 기준으로 문자열을 왼쪽, 오른쪽으로 나누었다.

그 후 정방향이동거리, 반대방향 이동거리를 구해 가로 이동거리의 최솟값을 구했다.

반복문을 이용하여 문자열의 연속된 A를 모두 탐색해 가로 이동거리의 최소값을 구했다.

 

세로 이동거리는 sol1함수를 따로 구현해 구해주었다.(정방향 반대방향 상관없이 같은 값이 나오기 때문)

 

 

---

 

다른 사람 풀이

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

using namespace std;

int LUT[] = { 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;
    for (auto ch : name)
        answer += LUT[ch - 'A'];
    int len = name.length();
    int left_right = len - 1;
    for (int i = 0; i < len; ++i) {
        int next_i = i + 1;
        while (next_i < len && name[next_i] == 'A')
            next_i++;
        left_right = min(left_right, i + len - next_i + min(i, len - next_i));
    }
    answer += left_right;
    return answer;
}

 

int LUT[] = { 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 };
answer += LUT[ch - 'A'];

세로 이동방향을 구하는 함수를 따로 구현하지 않고, 배열을 만들어 해결하였다.

위의 배열을 사용하면, 세로 이동거리의 최단 거리를 구할 수 있다!

 

i + len - next_i + min(i, len - next_i)

정방향과 반대방향 중 최단거리를 구하는 부분이다.

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges