[Lv.2] 조이스틱 [프로그래머스_코딩테스트] [Greedy]

🔍 문제 요약

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

문제에서 주어진 대문자 알파벳으로만 이루어진 문장을 조이스틱을 커서처럼 좌우 위아래로 이동해서 알파벳을 조정하여 가장 빠르게 해당 문장과 동일하게 만드는 최적의 이동 수치 찾기

🧠 나의 접근 방식과 시행착오

먼저 생각했던 방법은 아래 코드처럼 위아래 이동에 먼저 포커스를 맞춰서 Count 계산을 시켰다.

 첫 번째 문제의 핵심인 위아래 이동에서 문제의 핵심은 위로 가는 경우와 아래로 가는 경우 중 더 이동횟수가 작은 경우를 찾는 것. 괜히 고민을 많이 하다 보니 좀 더 코드가 더 길어지긴 했는데 목표 알파벳을 알파벳의 중간 알파벳에서 얼마나 떨어져 있는지 체크해서 방향을 정하는 것을 생각했다. (막상 풀이를 보면 그냥 타겟 알파벳에서 A까지 이동 횟수와 타겟 알파벳에서 Z까지 거리 + 1 (A가 시작점)을 비교해서 짧은 것을 계산 하면 된다.)

 두 번째로 핵심은 좌우로 이동하는 부분인데 이 부분이 난관이었다. (사실 문제를 읽었을 때 이 부분을 놓쳤어서 좌에서 우로 그냥 쭉 이동하면서 하면 위아래만 신경 썼다가 다시 읽고 난관에 봉착..) 일단 간단하게 생각해서 A가 연달아 나오는 부분이 최대한 적어야 한다. (그래야 이동 횟수를 줄일 수 있으니깐) 또 생각을 해보면 우측으로 이동했다가 좌측으로 이동할 수도 있을까?라는 생각까지 미치게 되었다. (그러나 이렇게 되게 되면 이동횟수가 길어지게 될 것이라 이건 패스해도 되지 않을까 싶음)

 결국 고민을 해보다가 좌로도 이동하고 우로도 이동해야 하는 것을 모두 구조체에 남아서 Count를 저장시켜놓는 것까지만 일단 생각을 했었다. 문제 풀이에 시간이 너무 지체가 되어서 풀이를 보고 공부해보기로 결정.

using System;
using System.Collections.Generic;

public class Solution
{
    public struct JoystickCountData
    {
        public int UpDownCount { get; set; }
        
        public int LeftMoveCount { get; set; }
        
        public int RightMoveCount { get; set; }

        public JoystickCountData(int upDownCount, int leftMoveCount, int rightMoveCount)
        {
            UpDownCount = upDownCount;
            LeftMoveCount = leftMoveCount;
            RightMoveCount = rightMoveCount;
        }
    }
    
    public int solution(string name) {
        // 아스키코드 A = 65, Z = 90
        // 문제의 핵심.
        // 1. 첫 세팅된 단어는 A
        // 2. A에서 원하는 알파벳이 어느 방향으로 가까운지 결정 필요 (Z의 경우 아래로 한칸)
        // 3. 좌우로 이동도 카운트 추가 필요
        // 4. ZAAAZ라고 하면 제일 좌측에서 좌측으로 커서 이동시 제일 우측으로 커서가 이동하는게 효율적임.
        //    단어에 A가 포함된 경우가 관건일 듯 함. (이 부분 짜는게 문제일 듯)
        
        // 조이스틱 카운트
        int count = 0;
        List<JoystickCountData> countDataList = new List<JoystickCountData>();
        
        // 1. 커서가 각 단어 위치에 있을 때 알파벳 바꾸는 거 합산 (위, 아래 조이스틱 이동)
        for (int i = 0; i < name.Length; i++)
        {
            char targetChar = name[i];
            // 위 아래 조이스틱 이동 계산용
            int upDownCount = 0;
            
            // 같은 단어 A인 경우는 그냥 카운트 증가시키면 되므로 아닌 경우만 계산
            if (!targetChar.Equals('A'))
            {
                // 위, 아래 어디로 조이스틱 이동할 지는 알파벳의 중간 지점에서 원하는  
                int diffCount = ('Z' - 'A') / 2 - targetChar;

                if (diffCount > 0)
                {
                    upDownCount = targetChar - 'A';
                }
                else
                {
                    upDownCount = ('Z' - 'A' + 1) - (targetChar - 'A');
                }
            }

            int leftMoveCount = 0;
            int rightMoveCount = 0;
            int leftCursorIndex = i;
            int rightCursorIndex = i;
            
            while (--leftCursorIndex != i)
            {
                if (leftCursorIndex < 0)
                {
                    leftCursorIndex = name.Length - 1;
                }

                if (name[leftCursorIndex] == 'A')
                {
                    leftMoveCount++;
                }
                else
                {
                    break;
                }
            }

            while (++rightCursorIndex != i)
            {
                if (rightCursorIndex >= name.Length)
                {
                    rightCursorIndex = 0;
                }

                if (name[rightCursorIndex] == 'A')
                {
                    rightMoveCount++;
                }
                else
                {
                    break;
                }
            }
            
            countDataList[i] = new JoystickCountData(upDownCount, leftMoveCount, rightMoveCount);
        }
        
        // 2. 좌, 우 조이스틱 이동 계산
        
        // 3. total 계산
        
        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        string name = "JEROEN";
        Console.WriteLine(sl.solution(name));
    }
}

 

✅ 풀이 코드

풀이 코드를 보고 해석하기론 위아래의 이동은 위에서도 설명했듯이 타겟 단어가 A와 Z에 어디에 더 가까지 있는지 차이 비교를 해서 작은 걸로 더하면 된다. 핵심은 두 번째인데.. 일단 좌에서 우로 그대로 쭉 이동하는 것을 최대값 (사실상 문장의 길이)로 잡는다. 그리고 그 값과 최선으로 좌우 이동을 한 경우를 체크해서 가장 최선의 좌우 이동 값을 구한다. (사실 이부분은 코드만 봐선 이해가 잘 안되어서 좀 더 자세히 과정을 통해서 이해해보았다)

 

먼저 좌에서 우로 단방향으로 쭉 이동하는 경우는 이미 구했기에 그 외의 케이스인 A가 연속된 경우를 건너뛰게 좌로 돌아가는 경우이다. 위 두번째 스크린샷의 move = i + lenghth - next + Math.Min(i, lenghth - next); 가 아래의 예시의 2가지 케이스를 더한 거란 것을 알 수 있다.

 

ABAAAAB라고 하면

좌에서 우로 한 칸 갔다가 다시 좌로 가는 방법인

0 -> 1 -> 0 -> 6

두번째 방법이 애초부터 바로 6으로 갔다가 다시 왼쪽으로 가는

6 -> 0 -> 1 이렇게 2가지

 

한 줄의 코드이지만 아래의 두가지 케이스를 하나로 묶었다는 것...

case 1
i + i + (length - next)

case 2

(length - next) + (length - next) + i

 

그렇게 해서 나온 코드는 아래와 같다. (코드를 읽기 쉽게 짠다고 하면 위 두가지 케이스를 하나의 move로 묶지 않고 두 줄로 나눠서 했지 않았을까 싶긴 한 코드긴 하다.) (일단 한 줄에 두가지 이동 방법이 들어 있어서 혼동이 생길 수 밖에 없어 보이긴 했음)

public class Solution {
    public int solution(string name) {
        int answer = 0;
        int length = name.Length;

        // 1. 각 자리 문자 변경 (위/아래)
        for (int i = 0; i < length; i++) {
            char c = name[i];
            answer += Math.Min(c - 'A', 'Z' - c + 1);
        }

        // 2. 좌우 이동 최적화
        int minMove = length - 1;  // 일단 한쪽 끝까지 가는 방법

        for (int i = 0; i < length; i++) {
            int next = i + 1;

            // A가 연속되는 구간의 끝 찾기
            while (next < length && name[next] == 'A') {
                next++;
            }

            // i까지 갔다가 뒤로 돌아가는 케이스
            int move = i + length - next + Math.Min(i, length - next);
            minMove = Math.Min(minMove, move);
        }

        answer += minMove;

        return answer;
    }
}

 

🔄 정리

풀이 방법을 해결하지 못하고 gpt의 도움을 받아서 해결한 문제이나 좌우 이동의 경우 문제는 어떻게 해결할 지 생각하는 힘을 기르게 되는 듯 하다. 좌우의 이동의 경우 A의 연속된 부분을 무시하고 어디를 먼저 들리느냐의 차이가 있는 듯 하다. Greedy하게 접근하는 방법은 결국 최선의 선택을 하는 거에 포커스가 맞춰야 한다는 거가 이런 부분이지 않을까 싶다.