[프로그래머스 / 그리디(Greedy) /python] 조이스틱

로직

 

문제를 해결하기 위해서는 크게 두 가지를 구해야 한다.

 

기본 설정이 모두 A라고 했을 때 조이스틱을

 

1. 아래 혹은 위로 최소 몇 번을 움직여야 하는지

2. 옆으로 최소 몇 번을 움직여야 하는지

 

아래 혹은 위로

해당 문자의 아스키 값을 이용해서 구했다.

 

옆으로 

옆으로 가는 경우는 세분화 해보면 아래와 같다.

1. 한 쪽으로만 가는 경우

   (1) 왼쪽으로만
   (2) 오른쪽으로만

가장 왼쪽 혹은 가장 오른쪽에 연속된 A가 몇 개인지 확인한 다음 방향을 결정한다.

(연속된 A의 길이를 확인하는 이유는 A가 있는 구간은 굳이 조이스틱이 거쳐가도 되지 않기 때문에 최대한 A의 길이가 긴 곳의 반대방향을 선택한다.)

right_most_A = count_continuousA(reversed(name))
left_most_A = count_continuousA(name[1:])

def count_continuousA(name, counter = 0):
    for c in name:
        if c != 'A': break
        counter += 1
    return counter

 

2. 한 쪽으로 가다가 백트레킹해서 다른 방향으로 가는 경우
   (1) 왼 오 왼
   (2) 오 왼 오

 

만약 BBBAAAAB와 같은 예시가 주어진다면 한쪽 방향으로만 가는 것보다는 왼쪽(뒤)로 갔다가 오른쪽(앞)으로 백트레킹하는 방식이 더 효율적이다.

 

백트레킹 시의 최소 거리를 구하기 위해서는 먼저 전체 문자열 중 연속된 A의 길이가 가장 긴 구간을 찾고 (안지나가도 되는 최대 구간을 찾는 것)

전체 문자열을 아래와 같이 크게 3등분으로 나눠서

|---front---|----A 구간----|----back---|

왼쪽 오른쪽 왼쪽 (front * 2 + back)으로 이동했을 때의 거리와 오른쪽 왼쪽 오른쪽 (back * 2 + back)으로 이동했을 때의 거리 중 가장 짧은 구간을 선택한다.

front = idx - 1
back = len(name) - (idx + max_len)

b_f_b = back * 2 + front
f_b_f = front * 2 + back

back_track_min = min(b_f_b, f_b_f)

def max_continuousA(name):
    #(start_idx, max_len)
    max_info = (-1, 0)
    for idx in range(len(name)):
        if name[idx] == 'A':
            length = count_continuousA(name[idx:])
            if max_info[1] < length:
                max_info = (idx, length)
    return max_info

1. 한 쪽으로만 가는 경우와 2. 백트레킹해서 다른 방향으로 가는 경우 중 가장 짧은 값을 선택한다.

 

 

전체 코드

def solution(name):
    ascii_val_A, ascii_val_Z = 65, 90
    up_and_down, left_and_right = 0, len(name) - 1

    for c in name:
        num_of_up = ord(c) - ascii_val_A
        up_and_down += ascii_val_Z - ord(c) + 1 if num_of_up > 13 else num_of_up

    right_most_A = count_continuousA(reversed(name))
    left_most_A = count_continuousA(name[1:])
    left = left_and_right - right_most_A
    right = left_and_right - left_most_A

    answer = min(left, right)

    max_info = max_continuousA(name)
    idx, max_len = max_info

    if idx > 1: # front 쪽으로 가려고 해도 막혀있뜸
        front = idx - 1
        back = len(name) - (idx + max_len)

        b_f_b = back * 2 + front
        f_b_f = front * 2 + back

        back_track_min = min(b_f_b, f_b_f)
        answer = min(back_track_min, answer)

    return answer + up_and_down

def count_continuousA(name, counter = 0):
    for c in name:
        if c != 'A': break
        counter += 1
    return counter

def max_continuousA(name):
    #(start_idx, max_len)
    max_info = (-1, 0)
    for idx in range(len(name)):
        if name[idx] == 'A':
            length = count_continuousA(name[idx:])
            if max_info[1] < length:
                max_info = (idx, length)
    return max_info