20240308_조이스틱(프로그래머스)

오늘의 TIL은 N으로 표현이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

 

문제 설명

조이스틱을 이용해서 알파벳 이름을 완성할 때 조작 횟수의 최소값을 구하는 문제.

초기 알파벳은 모두 A로 이루어져있으며

 

다음 알파벳으로 이동, 이전 알파벳으로 이동,

왼쪽 문자로 이동, 오른쪽 문자로 이동의 4가지 방향이 존재한다.

 

 

제한 조건

name은 알파벳 대문자로만 이루어져있다.

name의 길이는 1 이상 20 이하이다..

 

 

해결 방안

각 알파벳을 확인하여 M까지는 알파벳을 올리는 방식,

N부터 Z까지는 역으로 내리는 방식을 사용한다

또, A가 연속되는 경우에는 이를 왼쪽으로 이동하는 것과

오른쪽으로 이동하는 것 중에서 어느 방법이 더 적은 움직임인지 판단한다.

 

 

통과한 답안

using System;

public class Solution {
    public int solution(string name) {
        int answer = 0;
        
        for (int i = 0; i < name.Length; i++)
        {
            int count = Math.Min(name[i] - 'A', 'Z' - name[i] + 1);
            answer += count;
        }

        int minMove = name.Length - 1;
        for (int i = 0; i < name.Length; i++)
        {
            int next = i + 1;

            while (next < name.Length && name[next] == 'A')
            {
                next++;
            }

            int move = Math.Min(i, name.Length - next);
            int tmpMove = i + name.Length - next + move;
            minMove = Math.Min(minMove, tmpMove);
        }

        answer += minMove;
        
        return answer;
    }
}

 

 

단어를 만드는데 더 적은 움직이는 횟수 구하기

for (int i = 0; i < name.Length; i++)
{
    int count = Math.Min(name[i] - 'A', 'Z' - name[i] + 1);
    answer += count;
}

 

각 문자에 대해서 A에서부터 B, C, ... 으로 가는 것이 적은 횟수인지 Z, Y, X, ... 으로 가는 것이 적은 횟수인지

확인하여 그 값을 더하기

 

 

A가 연속되는 경우에 왼쪽과 오른쪽 중에서 더 적은 움직임 횟수 구하기

int minMove = name.Length - 1;
for (int i = 0; i < name.Length; i++)
{
    int next = i + 1;

    while (next < name.Length && name[next] == 'A')
    {
        next++;
    }

    int move = Math.Min(i, name.Length - next);
    int tmpMove = i + name.Length - next + move;
    minMove = Math.Min(minMove, tmpMove);
}

answer += minMove;

 

최소 움직임(minMove)를 name의 길이를 통해 구한 뒤에

만약 A가 연속되는 경우에는 알파벳을 변경하지 않아도 되기 때문에

어느 방향이 더 효율적인지 계산(tmpMove)한다.

 

이후 minMove와 tmpMove 중에서 더 적은 값을 선택한 뒤에 이를 answer에 더해서

 

글자를 변경하는 횟수와 글자를 이동하는 횟수를 더해서 최소값을 구한다.

 

 

오늘은 알파벳 A들로 기본값이 적용된 이름 기록에서

어떤 방식으로 이름을 지정해야 최소로 움직이는지를 구하는 문제를 풀었다.

 

이 문제를 풀면서 기본적으로 생각했던 부분은 알파벳을 올라가는 방법과 내려가는 방법 중에서

어느 방법이 더 적게 움직일 것인가 하는 부분이였으며,

이 부분을 구현한 뒤에 문제가 해결되지 않아 확인해보니

움직이는 횟수에도 역으로 움직이는 경우가 더 효과적인 경우가 있었다는 것을 알 수 있었다.

 

알파벳을 지정하는 것은 그리디가 아니였으나,

이후에 왼쪽으로 움직일지 오른쪽으로 움직일지를 선택하는 부분에서 그리디를 사용한다는 것을 알았고

이를 어떤 방식으로 구현할지 고민하다 위와 같이 각 경우의 수를 구하고 이 경우의 수들 중에서

최소값을 선택하는 방식으로 구현하였다.

 

알고리즘 문제를 풀면서 접하게 되는 특정한 이름이 붙은 문제 풀이법들을 많이 접하게 되는데

문제를 풀기에 급급해서 해당 지식을 정확히 습득하지 못한 부분이 있다고 느껴진다.

오늘부터는 시간적으로 여유가 있기 때문에 이러한 지식들을 좀 더 학습할 수 있는 기회를 가지려고 한다.