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

풀이

정답이지만 비효율적인 코드이다.
매 순간마다 양 옆에 'A'가 아닌 글자 중에 더 가까운 곳을 선택한다.
이렇게 되면 왔다갔다하면서 한번만 가도 될 길에 여러번 갈 수 있다.
또한 출발시점에서 더 먼곳을 먼저 가는갈때 최소이동횟수를 만드는 케이스도 있다.
그리디 알고리즘 문제이지만 매번 어디를 갈지 하는 선택을 그리디로 하면 안된다.
모든 'A'가 아닌 위치를 각각 먼저가는 것을 검사하면 정답이나온다.

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

int name_size=0;
string name;

int search(int start_cursor,int f_ans){
    vector<bool>chk;
    chk.resize(name_size);
    int answer = f_ans;
    int com_cnt=0;
    int cursor = start_cursor;
    
      for(int i=0;i<name_size;i++){
        if(name[i]=='A'){
            chk[i]=true;        
            com_cnt++;
        }
    }
    
    while(com_cnt!=name_size){
         //알파벳 맛춤
        
        if(!chk[cursor])
        {    answer+= name[cursor] - 'A'<'Z' - name[cursor] +1? name[cursor] - 'A' :'Z' - name[cursor]+1;
         com_cnt++;
        }
        chk[cursor]=true;
        
        //양 옆으로 체크해서 더 가까운쪽으로 이동
        if(com_cnt==name_size)
            break;
        //오른쪽으로 체크
        int right_move = 0,left_move=0;
        int right_cnt=0;
        for(int i=cursor ;right_cnt<=name_size;i++){
            if(!chk[i]){
                right_move=i;
                break;
            }
            right_cnt++;
            if(i==name_size-1)
                i=-1;
        }
        //왼쪽으로 체크
        int left_cnt =0;
        for(int i=cursor ;left_cnt<=name_size;i--){
            if(!chk[i]){
                left_move=i;
                break;                
            }
            left_cnt++;
            if(i==0)
                i=name_size;
        }
        if(right_cnt<left_cnt)
        {  
            cursor=right_move;
            answer+=right_cnt;
        }
        else
        {   
            cursor=left_move;
            answer+=left_cnt;
        }
        
    }
    return answer;
}
int solution(string input_name) {
    int ans=0;
    int result1=0;
    int result2=0;
   name_size= input_name.size();
   name=input_name;
    
    ans=search(0,0);
    for(int i=0;i<name_size;i++){
        ans = min(ans,search(i,min(i,name_size-i))); 
    }
    
    return ans;
}

다른 사람의 풀이

*A가 아닌 것은 편의상 B라고 부른다.
전체 구간중에서 방문하지 않아도 되는 구간이 있다. 그건  B와 B사이 구간이다 (중간에 B가 없는)

그래서 이 구간을 안가면 a+b (1orb)구간만 지나가면 된다.
2개를 고려하면 모든 경로를 검사할 수 있다.
1. for문을 통해 B와 B사이의 구간을 정한다. (*B는 이 사이에 없다)이 구간은 지나지 않는다.
2. 이 구간을 만나면 반대 방향으로 간다. 
3. 오른쪽으로 먼저 갔다가 왼쪽으로 가면 1구간을 2번 지나게 되고
4. 왼쪽으로 갔다가 오른쪽으로 가면 2를 두번 지나게 된다. 
5. 3,4 중 어떤것이 더 작은지 min함수를  통해 선택한다. 
코드에서 a,1 == i , b,2==len-next_i 이다.

 

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