[Python] 프로그래머스 - 조이스틱(미해결)

1. 문제정보

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

프로그래머스

 

2. 해결과정

시작 인덱스(0)에서부터 'A'가 아닌 가장 가까운 인덱스를 찾아 해당 인덱스로 이동하고, 일치하는 알파벳으로 변환하기 위한 최소 이동(커서를 아래로 움직일지, 위로 움직일지)횟수를 계산하는 문제다. 구현에 번거로움이 조금 있었지만 잘 구현했다고 생각했는데 채점 과정에 문제가 조금 있는 것 같다. (질문게시판에도 이게 왜 그리디인지 문의가 많았다..) 채점 과정에 문제가 있는 이유는 동일한 "가장 가까운 인덱스"가 2개 이상일 때 정답이 다르게 나오기 때문이다. 아래 예시 참고

 

ABAAABB
# 인덱스 이동이 0 -> 1-> 6 -> 5인 경우 = 7
# 인덱스 이동이 0 -> 6-> 5 -> 1인 경우 = 8

 

그리디로 해결이 실패한 분들이 DFS로 많이들 해결하시는 것 같다. 나중에 DFS로 한번 더 풀어봐야겠다.

 

3. 소스코드(실패)

import math
def solution(name):
    not_a_index = []
    for i in range(len(name)):
        if name[i] != 'A':
            not_a_index.append(i)
    
    # 현재인덱스
    index = 0
    
    # 전체 이동횟수
    answer = 0
    
    while not_a_index:
        print("A가 아닌 인덱스", not_a_index)
        print(name)
        # 1. 가장 가까운 인덱스찾기
        min_diff = len(name)
        closest_index = 0
        for i in not_a_index:
            diff = int(math.fabs(i-index))
            diff = min(diff, len(name)-diff)
            if diff < min_diff:
                closest_index = i
                min_diff = diff
        print("현재위치", index, "가장 가까운 위치", closest_index, "거리", min_diff)
        
                
        # 2. 이동횟수 계산, 현재인덱스 이동
        index = closest_index
        answer += min_diff
        print("현재위치", index, "가장 가까운 위치", closest_index, "거리", min_diff, "위치 이동후 이동횟수", answer, "알파벳", name[closest_index])
        answer += min(ord(name[closest_index])-ord('A'), 26-(ord(name[closest_index])-ord('A')))
        print("현재위치", index, "가장 가까운 위치", closest_index, "거리", min_diff, "알파벳 이동후 이동횟수", answer, "알파벳", name[closest_index])
        
        # 3. 이동한 인덱스 제거
        not_a_index.remove(closest_index)
    return answer

 

 

4. 배운점

현재 위치에서 최선의 선택을 구하는 법(위치 이동, 알파벳 변환 등)에 대해 한번 더 배우게 되었다. 또한 파이썬에서도 ord 함수를 통해 문자를 유니코드 값으로 변환할 수 있다는 것을 알았다.