프로그래머스 LV2. 조이스틱 - 그리디

		# 아래 3가지 경우 중 최소 이동 값으로 갱신
        # 1. 이전 커서 이동 값 ( 초기값 - 이름의 길이 - 1 )
        # 2. 연속된 A의 왼쪽 시작
        # 3. 연속된 A의 오른쪽 시작
        cursor_move = min([ cursor_move, 2 * i + len(name) - next, i + 2 * (len(name) - next) ])

 

프로그래머스 LV2. 조이스틱 - 그리디 문제 입니다. 이게 LV2..? 라는 생각이 드네요. 왼쪽과 오른쪽으로 커서가 이동하면서 최소를 구해야하는 걸 떠올리기가 쉽지 않았습니다.

 

 

그래서 일단 박치기를 해봤어요. 2개로 나눠서

 

1)  A 에서 문자로 변경하는 횟수

2)  오른쪽으로 가면서 바꾸는 게 빠른지, 왼쪽으로 가면서 바꾸는 게 빠른지 둘 다 구하고 min 때려서 더하기

 

로 풀었습니다. 2번은 더 효율적인 게 있을 수도 있을 것 같은데, 저는 잘 모르겠어요.

 

 

1) 같은 경우는 C나 C++은 그냥 아스키로 하겠지만, 파이썬은 ord 라는 함수를 사용해줘야 합니다.

2) 는 맨 처음에는 단순히 오른쪽과 왼쪽만 생각했는데, 이게 틀리더라구요

def solution(name):
    answer = 0
    length = len(name)

    # 1) A부터 문자 맞추는 상하 조이스틱 횟수
    # 위 아래 둘 다 구해보고 작은 값 더하기
    for char in name:
        up = ord(char) - ord('A')
        down = ord('Z') - ord(char) + 1
        answer += min(up, down)
    
    # 2) 커서를 이동하여 모든 변경이 필요한 문자를 방문하는 데 필요한 최소 조작 횟수 계산
    move = length - 1 # 좌우는 단순히 length - 1 보다 클 수 없다
    
    for i in range(length):
        idx = i + 1
        # A가 아닌 인덱스를 찾는 것
        while idx < length and name[idx]=='A':
            idx += 1

        right = idx - i
        left = 2 * i + (length-idx)
        
        move = min(move, right, left)
        
    answer += move
    
    return answer

 

딱 생각해봐도 좌우에서 틀린 것 같아요. 생각을 해보면 단순히 왼쪽이나 오른쪽이 문제가 아니였습니다.

 

예를 들어 SONGAAAAAAABLOG 라고 하면?

→ : S -> O

→ : O -> N

→ : N -> G

← : N <- G 

← : O <- N

← : S <- S

← : G <- S

← : O <- G

← : L <- O

← : B <- L

 

이런 식으로 좌우가 섞일 수 밖에 없단 말이죠? 조금 더 복잡한 케이스를 고려해보면 A 사이에 다른 문자가 껴있는 경우도 있겠죠. 결국 최솟값을 계산하기 위해서는 오른쪽이나 왼쪽으로만 이동하는 게 아니라, 그 위치까지 가는 모든 커서의 경우의 수를 고려해야합니다. 또한 처음부터 왼쪽으로 이동할 수도 있죠.

 

그런데 도저히 이걸 구현하는 로직이 생각이 안나는거에요. 그래서 단기간에 공부를 하기 위해 해설을 좀 봤습니다ㅋ

		# 아래 3가지 경우 중 최소 이동 값으로 갱신
        # 1. 이전 커서 이동 값 ( 초기값 - 이름의 길이 - 1 )
        # 2. 연속된 A의 왼쪽 시작
        # 3. 연속된 A의 오른쪽 시작
        cursor_move = min([ cursor_move, 2 * i + len(name) - next, i + 2 * (len(name) - next) ])

[프로그래머스] level.2 조이스틱 ★

 

위 블로그에서 그림까지 써서 자세히 설명을 해주고 있습니다...

 

저는 위 블로그랑은 조금 다르게 구현을 했습니다. 결국 A 연속 문자열이 나와야만 최솟값이 변화하기 때문에 A 연속 문자열까지 도달하는 거리를 정의했습니다.

 

만약 오른쪽으로 쭉 가는 방식으로 최단거리가 정의되면 그 값은 i가 될 것이고, 왼쪽으로 가는 방식으로 최단거리가 정의되면 length-idx 가 되겠죠.

 

그리고 전체적인 이동은 move 랑 i + length - idx + distance 중 작은 값을 선택하면 됩니다. 이걸 말로 풀어낼 자신이 없는데 위 링크의 그림을 보시면 이해가 잘 됩니다!

def solution(name):
    answer = 0
    length = len(name)

    # 1) A부터 문자 맞추는 상하 조이스틱 횟수
    # 위 아래 둘 다 구해보고 작은 값 더하기
    for char in name:
        up = ord(char) - ord('A')
        down = ord('Z') - ord(char) + 1
        answer += min(up, down)
    
    # 2) 커서를 이동하여 모든 변경이 필요한 문자를 방문하는 데 필요한 최소 조작 횟수 계산
    move = length - 1 # 좌우는 단순히 length - 1 보다 클 수 없다
    
    for i in range(length):
        idx = i + 1
        # A 연속 문자열 찾기 -> A 연속 끝나는 인덱스를 찾는 것
        while idx < length and name[idx]=='A':
            idx += 1

        distance = min(i, length - idx)
        # A 문자열 왼쪽부터 가는 게 가까운지 오른쪽부터 가는게 가까운지
        move = min(move, i + length - idx + distance)
        
    answer += move
    
    return answer

 

 

이렇게 풀어냈고... 이거 그리디 맞나요? 그냥 완전탐색에 가까운 것 같은데요 하하... 아직 DFS BFS DP 들어가지도 못했는데 어렵군요. 하지만 코테는 꾸준히 하면 늘거라고 믿고 있습니다.