프로그래머스 - lv2 조이스틱

조이스틱

문제는 프로그래머스에서 확인 할 수 있다.

✔ 접근방법

1. name 에서 가장 긴 A문자열 뭉치를 찾는다.
2. 좌/우 방향 이동에 따른 횟수를 구한다.
   2-1. 정방향으로 진행하였을 때의 이동횟수
   2-2. 정방향으로 진행하다 'A'를 만나고 역방향으로 진행하는 이동횟수
3. 상/하 방향 이동에 따른 횟수를 구한다.
   3-1. 알파벳 순으로 탐색했을 때의 횟수
   3-2. 알파벳 역순으로 탐색했을 때의 횟수

✔ 코드

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

using namespace std;

int findIdx(vector<char>& arr, char a){
    int ret = 0;
    for (int i=0; i<arr.size(); i++){
        if( arr[i] == a){
            ret = i;
        }
    }
    return ret;
}

int solution(string name) {
    /*
        케이스   
            1) A 뭉치가 여러개인 경우     ex) BBAABBBBAAAB
            2) A 뭉치가 연결되어 있는 경우 ex) AAABBAAAAA , AAAAABBAAA
            3) A 가 마지막에 있는 경우 ex) BBAAAABBAAA
    */

    int answer = 0;

    vector<char> arr        = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    vector<char> revers_arr = {'A','Z','Y','X','W','V','U','T','S','R','Q','P','O','N','M','L','K','J','I','H','G','F','E','D','C','B'};
    
    // 1 step : 문자열 중 A가 연속인 뭉치 중, 가장 긴 뭉치 찾기
    
    int A_num=0, max_A_num=0;
    int startIdx=-1, max_startIdx=-1;
    int endIdx=-1, max_endIdx=-1;

    for (int idx=0; idx<name.length(); idx++){
        if( name[idx] == 'A' ){
            A_num++;
            if( startIdx == -1 && endIdx == -1){
                startIdx = idx;
            }
            else if( startIdx != -1 && endIdx != -1){
                startIdx = idx;
            }
        }
        if( name[idx+1] != 'A' ){
            if( startIdx != -1 && endIdx == -1){
                endIdx = idx;
                if( max_A_num < A_num ){
                    max_A_num = A_num;
                    max_startIdx = startIdx;
                    max_endIdx = endIdx;
                }
                A_num = 0;
                startIdx = -1;
                endIdx = -1;
            }
        }
    }

    // 2 step : 시작점에서 A까지 정방향으로 가는 거리와 정방향으로 가다 역방향으로 가는 거리 중 가까운 거리 찾기

    int distance = name.length();
    int tail_A_size = 0;
    if( name[name.length()-1] == 'A'){
        for( int i=name.length()-1; i>=0; i--){
            if( name[i] == 'A' ){
                tail_A_size++;
            }
            else{
                break;
            }
        }
    }

    if( max_A_num != 0){
        answer = min(name.length()-1-tail_A_size , ((max_startIdx-1) * 2) + (name.length()-1)-(max_endIdx) );
    }
    else {
        answer = name.length()-1;
    }
    
    // 4 step : 위/아래 횟수 계산
    for (int i=0; i<name.length(); i++){
        if( name[i] != 'A'){
            answer += min(findIdx(arr, name[i]), findIdx(revers_arr, name[i]));
        }
    }

    return answer;
}

int main(void){

    string name = "CANAAAAANAN";
    int ret;

    ret = solution(name);
    cout << ret << endl ;

    return 0;
}

☝ 팁

문제해결까지 많은 시간이 걸렸었다.
문제의 조건 중 첫번째 자리에서 왼쪽으로 이동시 마지막 자리로 이동할 수 있다는 조건이 있다.
이 조건을 보고 당연히 마지막 자리에서 오른쪽으로 이동해도 첫번째 자리로 올 수 있다고 생각했다.
하지만, 이러한 조건은 문제에 없었다.

어쩌면 문제에 명시되어있는
이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요. 라는 문장에서 최솟값 부분이 오해의 소지가 많을수도 있을 것 같다.

👍 참고 사이트

• 프로그래머스