[프로그래머스 / 고득점 kit] 탐욕법: 조이스틱 ver2

0. 문제링크 1. 풀이방법 설명 2. 코드첨부

 

0. 문제링크

 

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

코딩테스트 연습 - 조이스틱 | 프로그래머스

1. 풀이방법 설명.

 

쉬운 줄 알고 풀었는데 밤새 풀었다..

 

시작은 A가 아닌 알파벳이 많은 곳으로 시작한다.

 

최초 방향이 결정된 이후 진행하다가 돌아가야 할 경우에 그 방향으로 진행한 후 종료 된다.

 

즉, 최초에 왼쪽 아니면 오른쪽으로 진행하고 백워드는 0회 아니면 1회이다.

 

최초의 기준은 name[1: ]에 대하여 반으로 쪼갠 후 반씩 확인한다.

짝수개일 경우에는 정확하게 쪼개면 되고 홀수 개일 경우 중간값을 버리고 쪼개면 된다.

 

백워드의 기준은 A가 아닌 알파벳이 나올때까지 걸리는 이동 횟수와 0인덱스로 이동하는 횟수 +1 을 비교하여 결정한다. 

 

예시

[A B B A A A A A A A B ]

 0 1 2  3 4 5 6  7 8 9 10 

 

반을 기준으로 왼쪽에 2개 오른쪽에 1개 이므로 왼쪽으로 시작한다.

이후 i가 2가 된 후 백워드를 검사시 A가 아닌 알파벳이 8번 이동해야 나오고 돌아갈 경우 3번 이동하면 된다. 따라서 백워드로 진행된다.

 

# 추가 고민사항

[A B A A A A A A A A B ]

 0 1 2  3 4 5 6  7 8 9 10 

 

다음과 같은 경우에 A 가 아닌 알파벳의 개수가 동일하여 어디로 시작하든 상관없다.

 

[A A B A A A A A A A B ]

 0 1 2  3 4 5 6  7 8 9 10 

 

하지만 다음과 같은 경우 개수는 동일하지만 백워드를 했을때 왼쪽 방향을 최초방향으로 하는 것이 유리하다.

하지만 프로그래머스에서는 이것에 대한 테스트케이스를 넣지 않은 것으로 보인다.

이런 케이스까지 고려한다면 단순한 풀이는 최초 방향을 두가지로 둘다 돌려보고 최소값을 사용하면 될 것 같다.

 

[A A B A B A A A A B B ]

 0 1 2  3 4 5 6  7 8 9 10 

이런 경우는 백워드가 필요없는 경우이어서 괜찮지만 백워드가 발생하는 경우에는 위에서 고민한 부분들을 해결하는 방법이 필요할 것으로 파악된다.

 

 

2. 코드첨부

# make alpabet dict
alpha_dict = {} 
i = 0
for x in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": 
    if i <= 13: 
        alpha_dict[x] = i 
    else: 
        alpha_dict[x] = 26-i 
    i +=1 

def solution(name): 
    move = 0 
     
    # if len(name) == 1  finish
    if len(name) == 1: 
        return alpah[name[0]] 
     
    # if len(name) > 1 
    len_name = len(name) 
    
    # check not_A_count for name[1:] 
    left_not_A_count, right_not_A_count = check_not_A_count(name) 
    
    # use 0 index
    move += alpha_dict[name[0]] 
    
    # if half left have more not A alphabet
    if left_not_A_count < right_not_A_count: 
        
        # start index
        i = 0
        
        # while loop
        while (i < len_name-1 ) and  (name[i+1:len_name].count('A') != len(name[i+1:len_name])):
            
            # backward check
            if i+1 < len_name-1 :
                
                # make move count list 
                lst = [k+1 for k in range(len(name[i+1:])) if name[i+k+1] != 'A']

                #  backward is better than moving right side
                if len(lst) != 0 and i+1 < lst[0]:
                    
                    # move from i index to 0 index 
                    move += i
                    
                    # set left limit 
                    l_limit = i+1
                    
                    # start point reset
                    i = len_name

                    # move to left side 
                    while l_limit < i and name[l_limit:i].count('A') != len(name[l_limit:i]):
                        # move left alphabet
                        i -= 1 
                        move +=1 
                        
                        # find alphabet 
                        move += alpha_dict[name[i]] 

                    return move

            i += 1 
            # next alphabet 
            move +=1 
            # find alphabet 
            move += alpha_dict[name[i]]         
                       
    else : 
        
        # start point set 
        i = len_name
        
        # move to left side loop
        while 1 < i and  name[1:i].count('A') != len(name[1:i]): 

            # backward check
            if 1 < i+1 :
                
                # make list having move count for not A
                lst = [k+1 for k in range(len(name[1:i])) if name[i-k-1] != 'A']
            
                # backward is better than move to left side
                if len(lst) != 0 and len_name-i+1 < lst[0]:
                    
                    # move to 0 index
                    move += len_name-i
                    
                    # right limit
                    r_limit = i
                    
                    # start point set
                    i = 0
                    
                    # while loop
                    while i < r_limit-1 and name[i+1:r_limit].count('A') != len(name[i+1:r_limit]):
                        # move right alphabet
                        i += 1 
                        move +=1 
                        
                        # find alphabet 
                        move += alpha_dict[name[i]] 
                        
                    return move
            
            # move left alphabet
            i -= 1 
            move +=1 
            
            # find alphabet 
            move += alpha_dict[name[i]] 
    
    # for case that does'nt have backward move
    return move 
     
     
def check_not_A_count(lst): 
    # check not A count 
    len_lst = len(lst) 
    # print("len_name:",len_name) 
    half_size = int((len_lst+1)/2)  

     # if len(name) -1 is even 
    if (len_lst-1) % 2 == 0: 
         
        # make [1:half_size] 
        half_left_list = lst[1:half_size] 
         
        # make [half_size:] 
        half_right_list = lst[half_size:] 
    else: 
         
        # make [1:half_size] 
        half_left_list = lst[1:half_size] 
         
        # make [half_size:] 
        half_right_list = lst[half_size+1:] 

    left_not_A_count = [1 for x in half_left_list if x != 'A']
    right_not_A_count = [1 for x in half_right_list if x != 'A']
     
    return len(left_not_A_count), len(right_not_A_count)