프로그래머스 - 조이스틱 Python

프로그래머스 - 조이스틱

문제유형 : 그리디 알고리즘, 파이썬

해결방법 1. 그리디

우선 입력받은 이름을 아스키코드로 변환해서 위, 아래 조이스틱으로 컨트롤 할 때의 최소값을 입력받는다. (‘A’: 65, ‘Z’: 90)

두가지 경우의 수로 나누어 볼 수 있다.

1. 입력받은 count 리스트 안에 0이 없다면 전체값을 더하고 나머지 글자까지 움직인 만큼 len(count) - 1을 더해주면 된다.
2. 리스트 안에 0 이 있는 경우 왼쪽과 오른쪽 중 덜 움직이는 곳으로 이동해가며 해당 인덱스 값을 0으로 바꿔주고, 이동값과 해당 인덱스에 해당하는 값을 더해주는 것을 전체 합이 0 이 될때까지 반복해주면 된다.

def solution(name):
    count = []
    for i in range(len(name)):
        count.append(min(ord(name[i]) - ord('A'), 91 - ord(name[i])))

    if 0 not in count:
        return (sum(count) + len(count) - 1)
    else:
        idx, answer = 0, 0
        while 1:
            answer += count[idx]
            count[idx] = 0
            if sum(count) == 0:
                break
            left, right = 1, 1
            while count[idx-left] == 0:
                left += 1
            while count[idx+right] == 0:
                right += 1
            if left < right:
                answer += left
                idx -= left
            else:
                answer += right
                idx += right
        return answer

"""
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉통과 (0.01ms, 10.2MB)
테스트 11 〉통과 (0.02ms, 10.1MB)
"""  

해결방법 2. BFS

bfs 방식으로도 풀이가 가능하다.

하지만 그리디 문제이만큼 위의 방법으로 푸는게 시간효율이 좋다.

import copy
def solution(name):
    moves = [-1, 1]
    nameList = list(name)
    # start = (nameList, index, count)
    def bfs(start):
        stack = [start]
        
        while stack:
            array, idx, cnt = stack.pop()
            cnt += min(ord(array[idx]) - 65, 91 - ord(array[idx]))
            array[idx] = 'A'
            if array.count('A') == len(array): 
                return cnt
            for move in moves:
                new_array = copy.deepcopy(array) 
                new_idx = idx + move
                new_cnt = cnt + 1
                stack.insert(0, (new_array, new_idx, new_cnt))

    return bfs((nameList, 0, 0))

"""
테스트 1 〉	통과 (0.05ms, 10.2MB)
테스트 2 〉	통과 (0.32ms, 10.3MB)
테스트 3 〉	통과 (0.04ms, 10.4MB)
테스트 4 〉	통과 (3.22ms, 10.3MB)
테스트 5 〉	통과 (12.28ms, 10.5MB)
테스트 6 〉	통과 (0.30ms, 10.3MB)
테스트 7 〉	통과 (3.34ms, 10.2MB)
테스트 8 〉	통과 (0.04ms, 10.3MB)
테스트 9 〉	통과 (0.31ms, 10.4MB)
테스트 10 〉통과 (0.03ms, 10.2MB)
테스트 11 〉통과 (0.36ms, 10.3MB)
"""