[Greedy Approach 예제] 프로그래머스 level2 조이스틱

문제

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

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

 

▲ - 다음 알파벳

▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

▶ - 커서를 오른쪽으로 이동

---

나의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    //(1) 처음 A로 이루어진 string 생성
    int first = name.size();
    string first_name;
    for(int i = 0;i<first;i++)
        first_name[i] = 'A';
    int i =0;
    //(2)하나씩 비교하기
    while(1){
    
    if(i == name.size() )
        break;
    
    
    if(first_name[i] != name[i]){
        //여기서 위아래 중 무엇이 더 좋은지 판단해야 한다. 
        //A 65 Z 90 90-65 = 25 65~77, 78~90
        if(name[i] < 78)
            answer += name[i] - 65 ;
        else if(name[i] > 77 )
            answer += 90 - name[i] + 1;
        } 
    else{//A인 경우
           answer++;
    }
    i++;   
    }      
    return answer;
}

조이스틱 이동방향은 4가지이다. 

(1) 위아래 이동 : 알파벳을 움직일 때 A, Z 둘 중 거리가 가까운 곳으로 위아래 이동을 결정한다.

(2) 좌우 이동 : 막연히 우로 이동한다고 판단했다. (여기서 실패)

 

왼쪽으로 이동하는 상황 : 현재 name[i] 값이 A인 경우

오른쪽 탐색과, 왼쪽 탐색을 하는 경우의 수를 비교하여, min 값을 출력해야한다. 

ex ) ABABAAAABA -> [좌 좌 위 우 우 우 위 우 우 위]

 

좌우 이동횟수가 최소가 되는 상황이 될 수 있는 경우는 다음과 같다.

1. 한쪽 방향으로만 이동할 때가 최소 

ex) JEROEN

2. 'A'로만 이루어진 문자열의 왼쪽을 먼저 탐색한 뒤 되돌아가 오른쪽을 탐색할 때가 최소 

ex) BBAAAAAAABBBB

3. 'A'로만 이루어진 문자열의 오른쪽을 먼저 탐색한 뒤 되돌아와 왼쪽을 탐색할 때가 최소 

ex) BBBBAAAAAAABB

 

1,2,3번을 구한 뒤 min값이 답이 된다.

 

if(name[i] == 'A')
{
	int target = i;
	while(target < name.length() && name[target] == 'A') 
      target += 1; //A로만 이루어진 문자열 찾기
      int left = i == 0 ? 0 : i - 1; //찾은 문자열 왼쪽에서의 이동횟수
      int right = name.length() - target;  //찾은 문자열 오른쪽에서의 이동횟수
      shift = min(shift, left + right + min(left, right)); //가장 작은값 찾기
        }

---

정답 풀이

    //(1) 상하 이동횟수
    for(auto c : name) {
    	answer += min(c - 'A', 'Z' - c + 1); 
    }
    
    
    //(2) 좌우 이동횟수
    //2-1 커서를 좌 또는 우 한 쪽 방향만으로 이동했을 때
    int shift = name.length() - 1; 
    for(int i = 0; i < name.length(); i++)
    {
        if(name[i] == 'A')
        {
            int target = i;
            while(target < name.length() && name[target] == 'A') {
            	target += 1; //A로만 이루어진 문자열 찾기
            }
            int left = i == 0 ? 0 : i - 1; //찾은 문자열 왼쪽에서의 이동횟수
            int right = name.length() - target;  //찾은 문자열 오른쪽에서의 이동횟수
            shift = min(shift, left + right + min(left, right)); //가장 작은값 찾기
        }
    }
    answer += shift;
    
    
    
    return answer;
}

(1) 상하 이동횟수도 새로운 string 생성없이 바로 셀 수 있다.

(2) 좌우 : 1,2,3에 따른 min값

reference https://unglog.tistory.com/8