프로그래머스 조이스틱

문제 이해하는 것도 좀 어려웠지만... 탐욕법(그리디 접근 방식)으로 저걸 어떻게 풀라는 지 생각도 안났다. 고민하다가 왼쪽으로만 이동하는 것과 오른쪽으로만 이동하는 것 그리고 왼쪽과 오른쪽 섞어서 이동하는 것 중에 최단 거리를 택하면 되겠다고 생각했다. 생각만 했고 구현하는 건 힘들었다.. 왼쪽과 오른쪽 섞어서 이동할 때 어떤 지점에서 다시 인덱스 0까지 돌아가야할 지 몰랐다. 인덱스 0부터 가운데까지 양방향으로 이동하면서 A가 아닌 알파벳이 나오면 leftDist, rightDist에 각각 거리를 넣었다. 이후 작은 값을 기준으로 돌게 되면 이동 거리가 최소화 된다. 둘 중 작은 거리 * 2 + 긴 거리를 하면 양 방향으로 이동했을 때 최단 거리가 나오게 된다. 물론 이 값과 왼쪽만으로 이동한 거리와 오른쪽으로만 이동한 거리 중 가장 작은 값을 찾아야 한다.

물론 아래 코드가 틀릴 수도 있다...

좌우로 이동하면 위치가 이동되고 상하는 알파벳이 변경된다. A인 경우 위치를 +1하면 B가 되고, -1을 하면 Z가 된다.

글자가 하나면 for문 돌릴 필요 없이 A로부터 얼마나 떨어져있는가를 아스키 코드 값의 차이로 계산하면 된다. 그리고 차이 값이 14 이상이면 전체 알파벳 수 26에서 차이 값을 빼준다. 이는 <-방향으로 가는 게 더 가깝기 때문이다.

글자가 하나가 아니면 인덱스 1부터 문자열 끝까지 돌아간다. <-방향과 ->방향을 동시에 돌면서 A가 아닌 알파벳이 나오면 거리를 rightDist, leftDist에 저장한다. <-방향과 ->방향 탐색 중 짧은 것을 dist에 넣는다. 첫번째 값과 A를 비교해서 result에 누적한다.

result에는 각 문자열과 A와의 아스키 코드 값 차이를 누적한다.

<- ->와 같이 한 방향으로만 가는 게 아닌 섞여서 왔다갔다 하는 것도 필요하다.

첫 인덱스를 제외한 나머지 값들 중에서 <-방향과 ->방향으로 동시에 가운데 값까지 가면서 A가 아니면 거리를 변경한다.

왼쪽으로 이동했을 때 A가 아닌 알파벳을 만나는 거리가 오른쪽의 그것보다 짧으면 여기서 돌면 된다. 그러므로 짧은 거리*2+반대편 거리를 하면 <-와 ->을 섞어가며 왔다갔다 했을 때 최적의 이동거리가 나온다.

요 거리와 <- 또는 ->이동만 했을 때의 최적 거리를 비교하여 짧은 것을 dist에 넣는다.

결과는 최단 좌우 이동 거리+각 문자와 A와의 아스키 코드 값 차이의 누적이 된다.

def solution(name):
    result=0
    if len(name)==1:#글자 하나면
        if ord(name[0])-ord('A')>13:#알파벳 거리 차이가 14이상이면
            return 26-(ord(name[0])-ord('A'))#알파벳 바꾸기
        else:
            return ord(name[0])-ord('A')
    for i in range(1,len(name)):#왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 이동
        if name[i]!='A':#오른쪽으로 이동 시 A가 아닌 문자의 마지막 위치
            rightDist=i
            print('rightDist',rightDist)
        if name[-i]!='A':
            leftDist=i
            print('leftDist',leftDist)
        if ord(name[i])-ord('A')>13:
            result+=26-(ord(name[i])-ord('A'))#알파벳 바꾸기
            print(name[i],result)
        else:
            result+=ord(name[i])-ord('A')
            print(name[i],result)
    if ord(name[0]) - ord('A') > 13:
        result += 26 - (ord(name[0]) - ord('A'))  # 알파벳 바꾸기
        print('0번째',name[0])
    else:
        result+=ord(name[0]) - ord('A')
        print('0번째',name[0])
    dist=min(rightDist, leftDist)
    for i in range(1,(len(name)-1)//2+1):
        if name[i]!='A':
            rightDist=i
        if name[-i]!='A':
            leftDist=abs(-i)
    if rightDist>=leftDist:
        dist=min(dist,2*leftDist+rightDist)
    else:
        dist=min(dist,2*rightDist+leftDist)
    print(result,dist)
    return result + dist

#print(solution("JAN"))
#print(solution("JEROEN"))
#print(solution("ABAAB"))
#print(solution("ABAAAB"))

https://programmers.co.kr/learn/courses/30/lessons/42860?language=python3