[Python][Greedy][BFS] 조이스틱

프로그래머스

Greedy 문제

프로그래머스

 

 

 

Greedy문제로 분류되어 있는데, Greedy로 풀 경우 최적해가 나오지 않는 경우가 있기 때문에 bfs로 푸는 사람들이 많은것 같다.

풀이 참고했던 두 가지 코드를 공유해본다

 

alpha = dict()

i = 65
for q in range(1,27):
    alpha[chr(i)] = q
    i += 1

r_alpha = dict()

i = 65
for q in range(1,27):
    r_alpha[q] = chr(i)
    i += 1

def solution(name):
    n = len(name)

    # 글자, idx, cnt
    temp = [['A'*n,0,0]]

    while True:
        word, idx, cnt = temp.pop(0)

        if name[idx] != word[idx]:

            word = word[:idx] + name[idx] + word[idx+1:]

            # 알파벳 이동 순서 결정
            if 26 - alpha[word[idx]] + 1 > alpha[word[idx]] - 1:
                cnt += alpha[word[idx]] - 1

            else:
                cnt += 26 - alpha[word[idx]] + 1

        # 탈출조건
        # 현재까지 이동한 값이 목표 값(name)과 같은지 확인
        if word != name:

            # 오른쪽 이동
            temp.append([word,(idx+1)%n,cnt+1])

            # 왼쪽 이동
            # 왼쪽 이동의 경우 0 - 1의 경우 존재하기 때문에 2가지 경우로 나눠서 확인
            if idx == 0:
                temp.append([word,n-1,cnt+1])
            else:
                temp.append([word,idx-1,cnt+1])
        else:
            break

    answer = cnt
    return answer

 

 

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

    def alphabet_to_num(char):
        num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
        return num_char[ord(char) - ord('A')]

    for ch in name:
        answer += alphabet_to_num(ch)

    move = n - 1
    for idx in range(n):
        next_idx = idx + 1
        while (next_idx < n) and (name[next_idx] == 'A'):
            next_idx += 1
        distance = min(idx, n - next_idx)
        move = min(move, idx + n - next_idx + distance)

    answer += move
    return answer