Greedy - 조이스틱

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

프로그래머스

이 문제는 다음과 같은 흐름으로 해결할 수 있다고 생각했다. 

1. 알파벳을 바꾸면서 조이스틱을 움직이는 횟수를 구한다.

2. 위 결과에 커서를 움직이면서 조이스틱을 움직이는 횟수를 구한다. 

 

1번 값을 구하는것은 쉬웠다. 

나는 딕셔너리로, 각 알파벳마다 몇 번의 움직임이 필요한지 횟수를 키-밸류 값으로 저장해놓고, input의 name 요소들을 반복문을 통해 

딕셔너리의 밸류 값들을 다 더해서 저장했다. 

(다른 사람들의 코드를 보니, 이 부분은 딕셔너리가 아닌 리스트를 이용해서도 풀 수 있다. 파이썬 내장 함수인 ord()를 이용하면 특정 알파벳의 순서를 구할 수 있다.)

 

2번 값을 구하는 과정은 어려웠다.

일단은 주어진 테스트 케이스를 만족하도록 경우를 나눠서 코드를 짜보고, 수정해 나가보자 라고 생각했다. 

 

그래서 처음에는 아래의 경우만 생각하고 코드를 짰다. 

만약 A가 없는 문자열이라면 커서는 정방향으로 하나씩 이동했을때 가장 움직임이 적다. ("JEOREN")

그리고 A가 들어있는 문자열이라면 정방향으로 하나씩 이동했을때의 횟수에서 -1 한다. ("JAZ")

이 방법은 당연히 위에 두 개의 케이스만 통과한다. 

 

일단 움직일 수 있는 방법은 정방향으로 쭉 가던지, 정방향으로 가다가 역방향으로 가던지, 처음부터 역방향으로 가다가 정방향으로 돌아오던지, 이렇게 세 가지 이다. 

그런데 이걸 어떤 경우에 방향의 전환이 일어나야하고, 코드로 어떻게 짜야하는지 감이 잡히지 않아서 구글링을 했다. 

 

우선, 방향의 전환이 일어나는 시점은 A 문자를 만났을 때 이다.

만약 A 들이 연속된다면, A 들은 문자를 변경할 필요가 없기 때문에 경우에 따라 A 들은 지나가지 않아도 움직임이 적을 수 있다. 

 

BBAABBB 를 예시로 위에서 말한 세 가지 움직임의 경우를 그림으로 볼 수 있다. 

 

1. 정방향으로 가기

A가 있든 없든 그냥 정방향으로 쭉 움직이는 경우이다. 

2. 정방향으로 가다가 역방향으로 가기

정방향으로 가다가 A를 만나면 역방향으로 방향을 전환하는 것이다. 

3. 역방향으로 가다가 정방향으로 가기

아예 처음부터 역방향으로 가다가 A를 만나면 정방향으로 돌아오는 것이다. 

위의 세 가지 경우를 모두 비교해서 가장 작은 움직임을 값으로 내면 된다.

 

코드로 나타내면 다음과 같다. 

def count_alph_change(alph):
    alph_dic = {'A':0, 'B':1, 'C':2, 'D':3, 'E':4, 'F':5, 'G':6, 'H':7, 'I':8, 'J':9, 'K':10, 'L':11, 'M':12, 'N':13, 'O':12, 'P':11, 'Q':10, 'R':9, 'S':8, 'T':7, 'U':6, 'V':5, 'W':4, 'X':3, 'Y':2, 'Z':1}

    return alph_dic[alph]

def solution(name):
    answer = 0
    n = len(name)
    move = n - 1

    # 알파벳 바꾸면서 생기는 조이스틱의 상하 움직임 횟수를 answer에 먼저 더해준다.    
    for alph in name:
        answer += count_alph_change(alph)
    
    for i in range(n):
        # next_i란 단순히 다음 인덱스가 아닌, 알파벳 변경이 필요한 다음 인덱스를 뜻함
        next_i = i + 1
        while next_i < n and name[next_i] == 'A':
            # 그렇기 때문에 next_i가 n보다 작고,
            # next_i의 자리가 A라면, A를 계속 건너뛰기 위해 아래와 같이 진행
            next_i += 1
        
        # 정방향으로 가기, 정방향으로 가다가 역방향으로 가기, 역방향으로 가다가 정방향으로 돌아오기
        # 세 가지 경우를 비교
        move = min(move, i + i + (n-next_i), i + (n-next_i) * 2)

    answer += move
    return answer

나는 알파벳을 변경하기 위한 스틱의 움직임을 구하는 함수를 (count_alph_change) 따로 정의 했다. 

이 함수는 알파벳이 input으로 들어오면 알파벳에 따라 스틱이 몇 번 움직이는지 그 횟수를 return 한다. 

 

solution 함수 안에서는 기본적으로 필요한 요소들을 정의해 주었다. 

move 는 움직임의 횟수를 기록하는 변수로, 최초에는 정방향으로만 움직였을 때의 횟수를 저장해 놓았다. 

이후에 move 는 계속해서 작은 값으로 갱신될 것이다. 

 

그 다음 알파벳을 변경하면서 생기는 스틱의 움직임 횟수를 먼저 answer에 저장한다. 

 

이제 인풋인 name을 인덱스를 이용해 반복문을 돌린다. 

반복문 안에 next_i 는 다음 인덱스 값을 의미 하는데, 알파벳 변경이 필요한 다음 문자의 인덱스를 뜻한다. 

그렇기 때문에 next_i 가 인덱스를 벗어나지 않았고 (next_i < n), name[next_i] 가 A 라면 A는 건너뛰기 위해 

next_i 의 값을 1씩 올려준다. 

그렇게 해서 A 아닌, 다음 문자의 인덱스 값을 찾게 되면 이제는 세 가지 이동 경우를 모두 비교해서 제일 작은 값을 move 에 갱신해 주는 것이다. 

 

2번의 이동방법(정방향에서 역방향으로)을 코드에서는 i + i + (n - next_i) 로 표현했다. 

그림을 보면서 생각하면 이해가 쉽다. i 가 0 일때는 좀 헷갈리니까 i 가 1 일때를 예시로 생각해보자. 

일단 정방향으로 움직이면서 i 까지 간다. 그리고 역방향으로 방향을 틀기 때문에 온 i 만큼 돌아가야 한다. 

마지막으로 next_i 까지 커서가 이동해야 하는데, 그 횟수는 n - next_i 와 같다. 

그렇기 때문에 i + i + (n - next_i) 가 된다. 

 

3번의 이동방법(처음부터 역방향으로 가다가 정방향으로 돌아오기)은 i + (n - next_i) * 2 로 표현했다.

이것도 i 가 1 일때를 예시로 생각해보면, next_i 는 연속된 A 다음에 오는 B의 인덱스(4)가 된다. 

2번 이동방법에서와 마찬가지로 next_i 까지 이동하는 횟수가 n - next_i 이고, 다시 정방향으로 돌아와서 맨 첫 문자까지 커서를 움직이는 그 횟수가 동일하게 n - next_i 이다. 그리고 마지막으로 커서를 i (=1) 번 움직이면 i 인덱스 위치까지 알파벳을 바꿀 수 있다. 

그렇기 때문에 i + (n - next_i) * 2 가 되는 것이다.

 

반복문 안에서 계속해서 제일 작은 값으로 move를 갱신시켜 주고,

마지막에는 알파벳 변경하기 위한 스틱 움직임 (answer) + 커서 이동하기 위한 스틱의 최소 움직임 (move) 를 더해주면 된다.