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

처음 작성한 코드

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

int solution(string name) {
    int answer = 0;
    vector<char> temp;
    int i = 0, dir = 1;
    while(true){
        if(name[i] >= 65 && name[i] <= 77){  // A에서 윗 쪽으로 이동하는 게 더 빠른 경우
            answer += name[i] - 65;
        }
        else{ // A에서 아랫쪽으로 이동하는게 더 빠른 경우
            answer += (91 - name[i]);
        }
        temp.push_back(name[i]);
        
        if(i == 0 && name[i+1] == 'A'){
            temp.push_back(name[i+1]);
            i = name.length();
            dir = -1;
        }
        
        if(temp.size() == name.length()) break;
        i = i + dir;
        answer += 1;
    }
    return answer;
}

 

 

0의 위치에 있고, 다음 문자가 A이면 방향을 돌리도록 한다. 

방향을 돌려야하는 경우에는 dir을 -1로 바꾸고, i를 name.length()로 해서 인덱스 값이 거꾸로 내려올 수 있도록 했다.

그리고 확인된 문자는 temp에 넣어 temp와 name의 크기가 같아지면 while문을 빠져나온다. 

테스트 1 〉	통과 (0.00ms, 3.77MB)
테스트 2 〉	통과 (0.00ms, 3.77MB)
테스트 3 〉	통과 (0.00ms, 3.74MB)
테스트 4 〉	통과 (0.00ms, 3.79MB)
테스트 5 〉	통과 (0.01ms, 3.79MB)
테스트 6 〉	통과 (0.00ms, 3.78MB)
테스트 7 〉	통과 (0.00ms, 3.78MB)
테스트 8 〉	통과 (0.00ms, 3.87MB)
테스트 9 〉	통과 (0.00ms, 3.8MB)
테스트 10 〉	실패 (0.03ms, 3.79MB)
테스트 11 〉	실패 (0.03ms, 3.75MB)

그런데 마지막 두 개의 케이스에서 실패가 떴다.  "AAABAAA" 와 "AAAAAABAA" 같은 경우를 생각하지 못했다.

방문 배열을 만들고 계속해서 체크해야하나 싶었는데, 그러면 while문을 빠져나오는 게 복잡하다.

그럼 어떻게 가야 효율적인지 어떻게 확인할 수 있을까. 

 

 

성공 코드

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

int solution(string name) {
    int answer = 0;
    string temp = string(name.length(), 'A');
    int index = 0, len = name.length();
    
    while(true){ 
        // A에서 올라가는게 빠른지, Z에서 내려가는게 빠른지 확인
        if(name[index] >= 'A' && name[index] <= 'M') answer += name[index] - 'A';
        else answer += ('Z'+1-name[index]);
        
        temp[index] = name[index];
        
        // temp와 name이 일치하면 모두 글자 확인한 것이므로 while문 탈출
        if(temp == name)  break;
        
        // 아직 temp, name 일치하지 않는다면
        // 현재 위치 index를 기준으로 오른쪽 문자와 왼쪽 문자 중에 누가 먼저 'A' 아닌 문자를 만나는지 확인
        else{    
            int left, right, i;
            for(i = 1; i < len; i++){
                left = (index - i + len) % len;
                right = (index + i + len) % len;
                if(name[right] != 'A' && name[right] != temp[right]) {
                    index = right;
                    answer += i;
                    break;
                }
                if(name[left] != 'A' && temp[left] != name[left]){
                    index = left;
                    answer += i;
                    break;
                }
            }
        }
    }
    return answer;
}

문자의 이동을 카운트하는 것은 간단하다. A에서 올라가는게 빠른지, Z에서 내려가는게 빠른지만 확인하고 answer에 값을 더해주면 된다. 

하지만 문제는 현재 인덱스에서 오른쪽 방향으로 가는게 빠른지, 왼쪽 방향으로 가는게 빠른지 확인해야한다. 

 

- 왼쪽으로 간다고 무작정 인덱스 값을 마이너스 하면 안된다. C++에서는 음수 인덱스가 적용되지 않기 때문에 name.length인 len을 더하고 다시 len으로 나눠서 허용 범위 안에서만 for문이 작동되도록 한다.

 

- right도 마찬가지로 범위 내에서 이동할 수 있도록 처리한다.

 

- 두 개의 포인터 left와 right 값이 바뀌면서 'A' 가 아닌 문자를 가장 먼저 만나는 포인터가 현재 인덱스에서 가장 가까운 곳으로 다음 인덱스가 된다. 

 

- 하지만 이 때, temp[left] 값과 name[left] 값이 같은지를 확인해야한다. 왜냐면 두 개의 값이 같다면 이미 조이스틱 처리를 거쳐간 문자이기 때문에 확인할 필요가 없다. 

 

- 그래서 조이스틱이 거쳐가지 않았으면서, 현재 인덱스 위치와 가장 가까운 위치가 다음 인덱스가 된다. answer에 인덱스에서 다음 인덱스까지의 차이인 i를 더하고 for문을 나온다.