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

 

틀린 풀이

def solution(name):
    
    answer = list("A" * len(name))
    count = 0
    i = 0 # 현재 인덱스
    
    while True :
    
        print("i: ",i)
        # 알파벳 변경하기
        if name[i] != "A" :
            count += min(ord(name[i]) - ord("A"), ord("Z") - ord(name[i]) + 1)
            answer[i] = name[i]
        
        # 다 만들었으면 반복문 탈출
        if ''.join(s for s in answer) == name :
            break
            
        left = right = 0
        

        # 왼쪽으로 이동하기 
        while True :
            if name[i-left-1] != "A" and answer[i-left-1] == "A" :
                left += 1
                break
            else :
                left += 1

        # 오른쪽으로 이동하기 
        while True :
            if name[(i+right+1)%len(name)] != "A" and answer[(i+right+1)%len(name)] == "A" :
                right += 1
                break
            else :
                right += 1

        count += min(left, right)
        if right > left : i -= left
        else : i += right
        if i < 0 : i = len(name)+i
        elif i >= len(name) : i = i%len(name)
        
    return count

• 그리디로 풀었더니 예외케이스가 발생했다.
• 나의 경우, 현재 위치에서 왼쪽, 오른쪽으로 갔을 때 더 빨리 A가 아닌 알파벳을 만나는 곳으로 이동한다.
• 즉, 그리디를 사용하여 풀었는데 이는 모든 테스트케이스를 충족하지 못해 다른 방법으로 풀어야 했다. (그렇다면 왜 그리디로 분류되었을까...? 의문이다...)
• 예외의 경우는 다음과 같다.  "BBBBAAAABA"
• 그리디로 푼 나의 경우엔 오른쪽3 , (왼쪽5 or 오른쪽5) 로 8 + 알파벳을 변경하는 횟수 5 = 13 이 나오는데,
• 최적의 경우, 애초에 왼쪽으로 먼저 가서 왼쪽2, 오른쪽5 + 알파벳변경5 = 12 가 되기 때문이다.
• 이를 해결하기 위해 다른 방법으로 풀어보았다. 

 

 

맞은 풀이

def solution(name):
    
    min_count = len(name) - 1
    alpha_count = 0
    
    for i, s in enumerate(name) :
        alpha_count += min(ord(name[i]) - ord("A"), ord("Z") - ord(name[i]) + 1)
        
        # 해당 알파벳 다음부터 연속된 A 찾기
        next = i+1
        while next != len(name) and name[next] == 'A' :
            next += 1
        
        min_count = min(min_count, i*2 + len(name)-next, 2*(len(name)-next) + i)
    
    return min_count+alpha_count

• min_count 를 순서대로 순회했을 때의 값으로 초기화한다.
• alpha_count 는 A에서 해당 알파벳으로 바꾸는 값이다.
• 연속된 A를 찾기 위해 next 변수를 둔다. 연속된 A 를 기준으로 왼쪽방향에서 시작한 것과, 오른쪽 방향에서 시작한 것 중 더 작은 것을 찾자.
• BCAAABCD 를 예로 들자.

• 위처럼 연속된 A의 왼쪽을 먼저 탐색하고, 오른쪽을 탐색하는 경우 i*2 + len(name)-next
• 연속된 A의 오른쪽을 먼저 탐색하고, 왼쪽을 탐색하는 경우 2*(len(name)-next) + i
• 또한, 연속된 A가 여러개 있을 수 있으므로 for 문을 통해 하나하나 탐색하면서, min_count 를 갱신하는 방법이다.