[코테] 99클럽 코테 스터디 16일차 TIL - Greedy

Question1 - [미들러] 조이스틱

 

문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/42860 

 

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

 

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

 

▲ - 다음 알파벳

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

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

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

 

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.

따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

---

문제풀이

 

trial 1

우선 조이스틱의 원리를 이해하는 것이 중요할 듯 하다.

문제는 전체 움직인 횟수의 count를 반환하라고 했는데, count를 두개의 차원으로 분리할 수 있다.

 

1) 조이스틱 상하 움직임 : 알파벳 찾기

매 주어진 자리에서 알파벳을 찾는다.

기본 주어진 디폴트 값이 A이므로, A에서부터 해당 알파벳까지 최소 이동값을 구한다.

이때 A에서 아래쪽으로 내려가는 것이 빠를지 아니면, A에서 Z로 한번 스틱을 올린 후 위로 올려가면서 찾는것이 빠를지, 두가지 경우의 수 중 선택이 필요하다.

나는 우선 알파벳 해시를 만들어 각 알파벳의 인덱스를 구한 후 위의 방식으로 최소값을 찾았다.

 

2) 조이스틱 좌우 움직임 : 자리 찾기 

좌우 움직임에서는 커서를 왼쪽, 오른쪽으로 이동하면서 바꿀 문자열의 자리를 찾는다.

여기서 고려해야 할 점은, 우선 오른쪽으로 한칸씩 모두 이동하면서 자리를 찾는 경우 기본 최소 이동 거리가 n -1이고, 

n-1을 기준으로 거리를 더 최소화 할 수 있는 지점과 비교하여 거리를 줄이는 방법이다.

예를 들어 문자열이 모두 A일 경우, 원래 디폴트값이 A이므로 커서를 모두 건너뛸 수 있다. 또한 맨 왼쪽부터, 혹은 오른쪽부터 커서를 움직이는 경우에 따라서 n - next_idx + i 가 거리가 될 수도 있다.

 

상하, 좌우의 움직임을 고려해서 아래와 같이 문제를 풀 수 있다. 

def solution(name):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    alpha_len = len(alphabet)  # 26
    
    alpha_hash = {}
    for idx, char in enumerate(alphabet):
        alpha_hash[char] = idx

    count = 0
    n = len(name)
    
    # 상하 이동의 최소 비용 계산 
    for i in range(n):
        a = alpha_hash[name[i]]
        count += min(a, alpha_len - a)
    
    # 좌우 이동의 최소 비용 계산
    min_move = n - 1
    for i in range(n):
        next_idx = i + 1
        while next_idx < n and name[next_idx] == 'A':
            next_idx += 1
        distance = min(i, n - next_idx)
        min_move = min(min_move, i + n - next_idx + distance)
    
    return count + min_move

 

 

 

*** 그리디 알고리즘 

 

그리디 알고리즘(탐욕 알고리즘)은 각 단계에서 현재 상태에서 가장 최적인 선택을 하는 알고리즘으로,

현재 선택이 그 이후의 선택에 영향을 주지 않고 최종적으로 최적해를 보장하는 경우에 사용한다.

 

간단히 말하자면 "각 단계에서 가장 좋은 선택을 하여 최종적인 해답도 최적이 되도록 문제를 해결" 한다는 의미이다.

지역적으로 최적의 선택이 전역적으로도 최적의 해답이 되는 경우.

 

위의 조이스틱 문제의 경우에도,

조이스틱 문제 전체 (총 이동 횟수)를 최소화 하기 위해 1) 상하 이동의 최소 이동 횟수 2) 좌우 이동의 최소 이동 횟수 를 구한 케이스로,

각 단계에서 '최소 비용'을 고려하여 최적화 한다는 의미에서 그리디 알고리즘이라고 볼 수 있을 것이다.

이 문제에서는 특히 거리를 계산할때 위에서부터, 아래에서부터 거리 중 짧은 거리를 더하고자 할 때  min(a, alpha_len - a) 식의 코드를 잘 활용했는데 다른 문제에서도 유용할듯 하다.

 

예시)

대표적인 그리디 알고리즘 문제 예시가 동전 반환 문제인데, 

최소한의 동전 개수로 특정 금액을 지불하는 것이 목표일 때, 아래처럼 동전을 크기 순으로 나열하여 가능한 한 가장 큰 가치의 동전을 사용하여 우선 지불해 나가는 방식이 그리디 방식이다. 

 

def min_coins(change, coins):
    coins.sort(reverse=True)
    
    num_coins = 0
    i = 0
    while change > 0 and i < len(coins):
        # 현재 동전으로 거스름돈 지불 최대 개수
        max_coins = change // coins[i]
        
        # 남은 거스름돈을 계산 및 이동
        change -= max_coins * coins[i]
        num_coins += max_coins
        i += 1
    
    return num_coins

# 예시: 36센트를 1, 5, 10, 20 센트 동전으로 지불
change = 36
coins = [1, 5, 10, 20]
print(min_coins(change, coins))  # 출력: 3 (20센트 동전 1개, 10센트 동전 1개, 5센트 동전 1개)