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

코딩테스트 고득점 Kit > 탐욕법(Greedy) > 조이스틱
https://school.programmers.co.kr/learn/courses/30/lessons/42860

해당 문제는 조이스틱을 상하로 움직여 알파벳을 맞추는 횟수 + 좌우로 움직여 이동하는 횟수의 최솟값을 구하는 문제입니다.

상하로 움직이는 최솟값은 쉽게 구할 수 있습니다.

문자열의 각 알파벳인 name[i]에 대해서
위로 조작 : name[i]-'A'과 아래로 조작 : 'Z'-name[i]+1 중 작은 값을 더해주면 됩니다.

---

좌우로 움직이는 최솟값이 어려운 부분인데, 저는 검색하면 주로 나오는 풀이랑은 조금 다르게 풀었습니다.

(1) i번째까지 오른쪽으로 이동했을 때 거리 right 를 구합니다. ((1.a)추가로 상하값도 더해줍니다.)
이때 i번째가 'A'라면 이전 값으로 설정합니다.

(2) i+1번째까지 왼쪽으로 이동했을 때 거리 left를 구합니다.
마찬가지로 i+1번째가 'A'라면 이전 값으로 설정합니다.

만약 문자열 AAAABBBAA가 있다면, 거리는 아래와 같습니다.

인덱스	0	1	2	3	4	5	6	7	8
right	(0)	0	0	0	4	5	6	6	6
문자열	A	A	A	A	B	B	B	A	A
left	5	5	5	5	4	3	0	0	(0)

(3) 마지막으로 배열을 순회하며 좌우 이동 최솟값을 구하면 됩니다.

i번째까지 오른쪽으로 이동했다가 반대로 이동하면 2*right[i] + left[i] 만큼,
i+1번째까지 왼쪽으로 이동했다가 반대로 이동하면 right[i] + 2*left[i] 만큼 최소로 이동합니다.

상단 표의 경우,

3번까지 오른쪽으로 이동(right[3] : 0)하고 다시 1번위치로 돌아왔다가
(이때 3번째까지 모두 A이므로 0*2)

3+1번까지 왼쪽으로 이동(left[3] : 5)하면
총 5회(2*0 + 5)움직이며, 해당 값이 최솟값입니다.

---

다른 예시는 아래와 같습니다.

인덱스	0	1	2	3	4	5	6	7	8
right	(0)	1	2	3	3	3	3	7	8
문자열	B	B	B	B	A	A	A	B	B
left	8	7	6	2	2	2	2	1	(0)

6+1번째까지 왼쪽으로 이동(left[6] : 2)하고 다시 1번위치로 돌아왔다가
6번 위치까지 오른쪽으로 이동(right[6] : 3)하면
총 7회(2*2 + 3) 움직이며, 해당 값이 최솟값입니다.

---

코드는 아래와 같습니다.

using System;

public class Solution {
    public int solution(string name) {
        int answer = 0;
        
        int n = name.Length;
        int[] right = new int[n];
        int[] left = new int[n];
        
        //(1)
        for(int i=0; i<n; i++)
        {
            if(i > 0 && name[i] == 'A') right[i] = right[i-1];
            else {
                right[i] = i;
                //(1.a)
                answer += Math.Min('Z'-name[i]+1, name[i]-'A');
            }   
        }
        
        //(2) 
        for(int i=n-1; i>0; i--)
        {
            if(name[i] == 'A') left[i-1] = left[i];  
            else left[i-1] = n - i;
        }
        
        //(3)
        int minMove = n-1;
        for(int i=0; i<n; i++)
        {
            int move = Math.Min(left[i]*2+right[i], left[i]+right[i]*2);
            minMove = Math.Min(minMove, move);
        }
        
        return answer+minMove;
    }
}

---

혹시 풀이에 문제가 있거나, 궁금한게 있으시다면 댓글 남겨주세요.