[프로그래머스/파이썬] 그리디 조이스틱

bye9·2021년 2월 17일
0

알고리즘(코테)

목록 보기
74/130

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


알고리즘 분류

  • 그리디

문제풀이

프로그래머스 내부에서도 논란이 많은(?) 문제이다.

상하로 움직여 최소로 알파벳을 조정하고, 좌우로 움직여 최소로 바꿀 알파벳 위치를 정하는 것 두 가지를 고려해야한다.

상하를 움직이는 것은 아스키코드 값으로 구해서 금방했는데 좌우가 너무 어려웠다...

오른쪽으로 A가 아닌 알파벳을 만날때까지 움직인 횟수를 right에 저장하고, 왼쪽으로 ...횟수를 left에 저장한다.

그리고 왼쪽이 더 가까운 경우 왼쪽으로 이동해서 돌려준다.

참고: https://blog.naver.com/jaeyoon_95/221740770765
https://programmers.co.kr/questions/12677


 프로그래머스에서 통과는 되지만 해당 코드는 틀린 점이 있다...
 "ABABAAAAAAABA"의 경우 11이 나오지만 정답은 10이다.
 첫번째 배열에 A 에서 보통 오른쪽으로 한 칸 이동하지만,
 처음부터 왼쪽으로 이동하여 오른 끝쪽에 있는 B를 먼저 찍고 오면 
 최단거리를 10으로 줄일 수 있는 것이다.. 

소스코드

def solution(name):
    name=list(name)
    target=list("A"*len(name))

    cnt=0
    index=0
    while True:
        right=1
        left=1
        if name[index]!=target[index]:
            temp=ord(name[index])-ord(target[index])
            cnt+=min(temp, 26-temp)
            name[index]="A"

        if name==target:
            break

        for i in range(1,len(name)):
            if name[index+i]=="A":
                right+=1
            else:
                break
        for i in range(1,len(name)):
            if name[index-i]=="A":
                left+=1
            else:
                break

        if right>left:
            cnt+=left
            index-=left
        else:
            cnt+=right
            index+=right

    return (cnt)

0개의 댓글