[프로그래머스] 조이스틱

잘못된 코드

def solution(name):
    #위 알파벳 다음 , 아래 알파벳 이전 , < 첫번째 위치면 마지막으로 커서 이동 >
    #name: 만들어야되는 것
    #return: 최소 횟수
    #1.해당 문자에서 A가 아닌 변경해야하는것의 위치
    #2.그 위치에 따른 최단 커서 이동
    #3.각 알팟에서의 최단 커서이동
    #jklmnopqrstuvwxyz
    count = 0
    abcstr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' # 26개 25:1
    abc = list(abcstr)
    lenName = len(name)
    nameArr = list(name)
    r = 0
    l = 0
    #a가 아닌것이 앞에서 가까운가 뒤에서 가까운가
    
    # 방향 처리
    for i in range(1,lenName):
        if name[i]!='A':
            r = i
            break;
    for i in range(-1,-(lenName),-1):
        if name[i]!='A':
            l = -i
            break;
    print(l,r)
    #더 적은곳으로 전진
    
    def getCount(spell):
        idx = abc.index(spell)
        return min(idx,26-idx)
    
    if l>=r:#우측 전진
        for i in range(0,lenName-(l-1)):
            if i != 0:
                count += 1
            if name[i] == 'A':
                count +=1
                continue
            count += getCount(name[i])
            
    if l<r:#좌측 전진
        for i in range(0,-(lenName-(r-1)),-1):
            print(i,'i')
            if i != 0:
                count += 1
            if name[i] == 'A':
                count +=1
                print(count)
                continue
            count += getCount(name[i])
            print(count)
            
    return count

이유

위 코드에서는 좌우 선택시 0인덱스로부터 가까이 있는 A의 갯수만을 고려했고 갔다가 돌아오는 경우를 고려하지 못했다.

BABBBBAAAABB 같은 경우가 예시이다.

 

한 방향으로 쭉 돌면서 확인 하는경우가 아닌 필요에 따라 갔다가 돌아오는 경우도 필요하다

 

결국 A가 많은 부분을 찾아서 

^BBBBBBAAAAAAAAABB

BBBBBBAAAAAAAAA^BB

BBBBB^BAAAAAAAAABB

 

순으로 탐색하는 방법이 정답이고 두가지를 고려해야한다 

1.연속되는 A를 피한다.

2. 방향 롤백시 최단거리를 고려한다.