[Programmers]탐욕법 > 조이스틱(c++)

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

코딩테스트 연습 - 조이스틱

 

아직 해결하지 못했다 ㅠㅠ 테스트케이스 23번만 계속 실패한다..

문제를 푼 사람들은 "ABABAAAAABA" 답이 11이라는데..

뒤에서부터 처리 후 다시 앞으로돌아가면 10이 나오는거 아닌가ㅠㅠ 모르겠다..

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

using namespace std;

int solution(string name) {
    int answer = 0;
    int right = 0;
    int left = 0;
    string name_back = name;
    for(int i=0;i<name.size();) {
        
        int cnt = 0;
        if(name[i]!= 'A') {
            cnt = name[i] - 'A';
        }
        if(cnt > 13) cnt = 26 - cnt;
        answer+= cnt + min(left, right);
        name[i] = 'A';
        
        if(count(name.begin(), name.end(), 'A') == name.size()) break;
        
        right = 1;
        left = 1;
        //오른쪽으로 가는 경우, 왼쪽으로 가는 경우
        for(int j=i+1, k=i-1;j>=0;j++,k--){
            
            j = j % name.size();
            if(k<0) k = name.size() +k;
            if(name[j] == 'A') right++;
            if(name[k] == 'A') left++;
            
            if(name[j] != 'A' ) {i = j; break;}
            if(name[k] != 'A' ) {i = k; break;}
            
        }
    }
    
    //뒤에서부터 출발하는 경우
    right = 1;
    left = 1;
    int answer_back = 0;
    for(int i=name_back.size()-1;i>=0;) {
        
        int cnt = 0;
        if(name_back[i]!= 'A') {
            cnt = name_back[i] - 'A';
        }
        if(cnt > 13) cnt = 26 - cnt;
        answer_back+= cnt + min(left, right);
        name_back[i] = 'A';
        
        if(count(name_back.begin(), name_back.end(), 'A') == name_back.size()) break;
        
        right = 1;
        left = 1;
        //오른쪽으로 가는 경우, 왼쪽으로 가는 경우
        for(int j=i+1, k=i-1;j>=0;j++,k--){
            
            j = j % name_back.size();
            if(k<0) k = name_back.size() +k;
            if(name_back[j] == 'A') right++;
            if(name_back[k] == 'A') left++;

            if(name_back[k] != 'A' ) {i = k; break;}
            if(name_back[j] != 'A' ) {i = j; break;}

            
        }
        
    }
    answer = min(answer, answer_back);
    
    return answer;
}


int main() {

    string name = "ABABAAAAABA";
    solution(name);
}