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

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

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

- Level2 Greedy문제이다. 시간복잡도는 conversion 호출에 O(N), 모든 문자열에 대해 탐색을 진행하므로 O(N) 해서 O(N^2)이다.

 

- 무난한 문제지만, 많은 사람들이 테케 11번을 통과 못하는 듯했다. 이유는 단방향으로 진행하는 코드를 작성해서인데, 이렇게 작성하면 안 되고 현재 알파벳을 원하는 알파벳으로 변경한 뒤, 오른쪽으로 가는 방향 뿐 아니라 왼쪽으로 이동해서 다른 문자를 탐색하는 과정도 동시에 이루어져야 한다는 것이다. 테스트케이스로 "ABAAAAAAAAABB" 의 return값을 7로 추가해 주어서 확인을 해 보는것이 좋다.

 

 

#include <algorithm>
#include <string>

using namespace std;
int answer = 0;
bool is_diff(string &a, string &b){
    if(a == b) return false;
    return true;
}
void conversion(int index, string& a, string& b){
    int first_diff = abs(a[index] - b[index]);
    answer = answer + min(first_diff, 26-first_diff);
    a[index] = b[index];
}
int solution(string name) {
    string now_str = "";
    for(int i = 0; i < name.length(); i++) now_str += 'A';
    int now_index = 0;
    conversion(now_index, now_str, name);
    int distance = 1;
    while(is_diff(now_str, name)){
        int first_index = (now_index+distance) % name.length();
        int second_index = now_index-distance;
        if(second_index < 0) second_index += name.length();
        if(now_str[first_index] != name[first_index]){
            conversion(first_index, now_str, name);
            now_index = first_index;
        }
        else if(now_str[second_index] != name[second_index]){
            conversion(second_index, now_str, name);
            now_index = second_index;
        } else {
            distance++; continue;
        }
        answer+=distance;
        distance = 1;
    }
    return answer;
}