[Algorithm🧬] 조이스틱

또상·2022년 3월 10일
0

Algorithm

목록 보기
45/133
post-thumbnail

문제 / 풀이.py

진짜 열심히 풀었는데.... 반이나 계속 안됨...

일단 내가 파악한 것은 A 가 연속으로 나올 때가 관건인 문제였다. 내가 짰던 알고맂므의 문제는, 문제에서 주는 JAZ 같은 케이스에서 1 정도 더 큰 답이 나온 다는 거였다. 테스트에 대한 케이스를 더 나눠서는 일반화가 불가능 할 것 같아서 다른 사람 풀이를 참고해서 풀었다. 일단 중간에 한번 테스트 케이스가 바뀌어서 그런지 찾아도 안되는 답이 굉장히 많았다...

알고리즘

그래서 여기 에서 참고했는데,

이런 알고리즘을 따르고 있다!!! 내가 코드를 길고 험난하게 짜긴 했지만 2번째 케이스까지는 고려를 했는데 3번재 케이스를 고려를 못해서 정답이 안나왔다는 것을 알 수 있었다.

코드

def solution(name):
    answer = 0
    
    # 정방향(좌->우)으로 움직이면 (길이 - 1) 회 움직임.
    min_move = len(name) - 1
    
    for i, c in enumerate(name):
    	# 알파벳 변경 : 상하 이동
        answer += min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
        
        # 해당 자리 다음에 A가 연속되는 문자열이 있다면 그 길이가 얼마인지 계산.
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        # 기존, 연속 A 왼쪽에서 접근해서 좌->우->좌 로 꺾을지, 연속 A 오른쪽에서 접근해서 우->좌->우 로 꺾을지
        # 여기에 min_move 가 들어가는 이유는, 현재까지 제일 작은거랑 새로운 두개의 루트 중 최소를 찾아야 하기 때문.
        min_move = min([min_move, 2 * i + len(name) - next : , i + 2 * (len(name) -next)]) 
        
    # 결과 : 알파벳 변경 + 좌우이동
    answer += min_move
    return answer

참고

https://velog.io/@jqdjhy/프로그래머스-파이썬-조이스틱-Greedy

profile
0년차 iOS 개발자입니다.

0개의 댓글