[프로그래머스] 탐욕법 - 조이스틱 (파이썬) - Statssy

25 Jun 2020 in Algorithm on 프로그래머스

코딩테스트 연습 - 탐욕법 - 조이스틱 (파이썬)

코딩테스트 연습 - 탐욕법 - 조이스틱를 풀어본다.

내 코드는 일단 테스트 11이 실패한다. 실패와 상관없이 내 코드는 틀렸다. 왜냐하면 ‘BBABAAAB’ 경우를 생각하지 못했기 때문이다. 그래서 이문제는 사실 그리디 문제가 아닌 BFS문제인거 같다.
질문하기에 다른분이 짜놓은 코드가 있어서 보려했지만 FLOW는 알겠지만 아직은 감이 안온다. BFS, DFS문제를 좀 풀어보고 이문제를 다시 보려 한다.
내 코드의 핵심은 오른쪽으로 쭉가는게 이득인지 왼쪽으로 쭉가는게 이득인지, 그리고 마지막에 A가 다수 나오면 그 만큼은 계산하지 않는다 라는 코드로 짰지만 다시 말하지만 ‘BBABAAAB’ 경우를 고려하지 않은 좋지않은 수였다.

내 코드

def locate(name, ord_lst):
    loc = 0
    right = 0
    left = 0
    cnt = 0
    for i in range(1, len(name)):
        if ord_lst[i] == 0:
            right += 1
        else:
            break
    for i in range(1, len(name)):
        if ord_lst[-i] == 0:
            left += 1
        else:
            break
            
    if right >= left:
        loc = -1
        cnt = right
    else:
        loc = 1
        cnt = left
    return loc, cnt


def solution(name):
    answer = 0
    ord_lst = []
    for s in [str(i) for i in name]:
        if (ord(s)-65) <= 13:
            ord_lst.append(ord(s)-65)
        else:
            ord_lst.append(-(ord(s)-65-26))
    
    loc, cnt = locate(name, ord_lst)
    answer = sum(ord_lst)+(len(ord_lst)-1)-cnt
    return answer

잘 푼 다른 사람 코드

import copy
def solution(name):
    moves = [-1, 1]
    nameList = list(name)
    # start = (nameList, index, count)
    def bfs(start):
        stack = [start]
        
        while stack:
            n = stack.pop()
            array, idx, cnt = n[0], n[1], n[2]
            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) # array 주소 복사 서로 영향 안미치게
                new_idx = idx + move
                new_cnt = cnt + 1
                stack.insert(0, (new_array, new_idx, new_cnt))

    return bfs((nameList, 0, 0))