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

 

 

유명한 그리디 문제!

고려해야하는 부분은 크게 두가지인데, 상하(A~Z)최소값과 좌우최소값이다.

 

1. 상하 최소 구하기

우선 쉬운것부터 고려하자면

상하 최소는 target에서 'A'까지의 거리와 'Z'에서 target까지의 거리를 비교해주고 최소값을 더해주면된다.

이때, 'Z'에서 거리를 고려하는 경우는 switch가 한번 일어나기 때문에 +1 해준다.

 

 

2. 좌우 최소 구하기

이 문제의 핵심이라고 할 수 있다.

우선, 좌우 경우의 수는 크게 두개로 볼 수 있다.

간단하게 순차 진행을 해버리느냐와 역행을 넣느냐 두가지로 나눠 볼 수 있다.

 

우리가 여기서 집중해야하는 경우는 역행을 넣었을 때, 역행을 언제 하냐에 포인트가 있다.

예를 들어, 'BBAAAAB'는 역행 후 다시 돌아와서 순차 진행을 하는 것이 최소값일 것이고,

'BAAAABB'는 순차 진행 후 역행을 하는 것이 최소값일 것이다.

 

그래서, 좌우 경우는 총 3가지의 경우의 수가 있음을 알 수 있다.

1. 순차 진행
2. 역행 진행 - 역행 후 순차
3. 역행 진행 - 순차 후 역행

첫번째 순차진행은 문자열의 길이 -1만큼의 이동이 일어나므로, shift를 순차진행값으로 초기화 해준다.

이 3가지 경우의 수 중에서 최소값을 더해주고, 맨 마지막에 각각의 문자열에 대한 상하 최소값들을 더해주면 된다!!

 

자 이제 3가지 경우의 수 중 최소값을 구하는 방법에 대해 알아보자.

우선, <역행>이 일어났다는 것은, 'A'문자열을 만났기 때문이다.

그럼 우리는 이 'A'를 기준으로 왼쪽 문자열과 오른쪽 문자열의 길이를 비교해서 더 짧은 쪽으로 먼저 진행하게끔 하면 된다!

• 'A'가 끝나는 길이 구하기 : target값을 잡아주고, while문을 이용해서 'A'문자열의 끝 인덱스를 얻는다.
• 'A'기준 왼쪽 문자열 : (처음에는 단순하게 i라고 생각했는데ㅋㅋ)
  'A'를 만난 이전의 문자열을 봐야하기 때문에, i-1을 해준다.
  대신, 'A'가 첫번째에 위치해 있는 경우는 i-1하면 -1이 되어버리므로 예외처리를 해준다.
• 'A'기준 오른쪽 문자열 : (처음에는 문자열 길이 - target -1이라고 생각했는데..ㅋㅋ)
  문자열의 길이 - target을 해주면 된다. 만약 'A'가 문자열의 끝인 경우를 생각하면 이해가 쉬워진다.

이제 3가지 값을 모두 구했으니, 이 세개중 min값을 구해주고, 루프의 밖에서 answer에 더해준다. (당연한 소리지만, 안그러면 shift 여러번 연산됨)

좌우 이동값은 이미 shift로 answer에 더해졌으므로, 각각의 문자열에 대한 상하 최소값만 추가로 더해주면 끝!

 

[ 전체 코드 ]

#include <string>
#include <vector>

using namespace std;
/*
1. 상하 최소 : min(target-'A', 'Z'-target+1)

2. 좌우 최소 [3가지 경우의 수]
-> 순차 진행, 역행 진행(2가지)
1) BBAAAAB - 역행 후 순차 진행이 더 나은 경우 
2) BAAAABB - 순차 진행 후 역행이 더 나은 경우
: 이 두가지는 앞뒤 'A'가 아닌 문자열의 길이 비교로 해결
==> 총 3개에 대한 min을 구해서 더해주기.
*/

int solution(string name) {
    int answer = 0;
    int shift = name.size()-1;
    for(int i=0; i<name.size(); i++) {
        if(name[i]=='A') {
            int target = i;
            while(target < name.size() && name[target]=='A') target++;
            int left = i==0? 0: i-1; //'A' 왼쪽 문자열 길이
            int right = name.size()-target; //'A' 오른쪽 문자열 길이
            shift = min(shift, left+right+min(left,right));
        }
    }
    answer += shift;
    for(auto x : name) answer += min(x-'A', 'Z'-x+1);
    return answer;
}