그리디 알고리즘 - 조이스틱

조이스틱

이것은.. H E L L

 

문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
name return
"JEROEN" 56
"JAN" 23

 

내가 푼 풀이

def solution(name):
    answer = 0
    name=list(name)
    name_reverse = name[::-1]
    num_list=[]
    print(name)
    a_num1 = 0
    a_num2 = 0 
    
    t1 = 0
    t2 = 1
    alphabet_reverse = ['Z','Y','X','W','V','U','T','S','R','Q','P','O','N','M','L','K','J','I','H','G','F','E','D','C','B','A']
    alphabet = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
    print(alphabet[9]==name[0],alphabet[9],name[0])
    for name_alphabet in name:
        for cursor in alphabet:
            if name_alphabet == cursor:
                num_list.append(alphabet.index(cursor))
        for cursor in alphabet_reverse:
            if name_alphabet == cursor:
                num_list.append(alphabet.index(cursor)+1)
        min_num=min(num_list)
        print(num_list)
        answer=answer+min_num
        num_list=[]
    for name_alphabet in name:
        t1 += 1
        if name_alphabet == 'A':
            while name_alphabet == 'A':
                a_num1+=1
                if name_alphabet != 'A':
                    break
        break

    for name_alphabet in name_reverse:
        t2 += 1
        if name_alphabet == 'A':
            while name_alphabet == 'A':
                a_num2+=1
                if name_alphabet != 'A':
                    break
        break
    print(a_num1, a_num2, t1, t2)
    if a_num1 <= a_num2:
        answer = answer+t1    
    else:
        answer = answer+t2
            
        
    return answer

 

내가 푼 풀이 해석

우선 문제를 이해하는 데에만 많은 시간이 소요됐다.

그리고 애초에 잘못 이해했다...

문제를 보고 머리에 풀이가 떠올랐을 때의 문제풀이 프로세스를 설명하자면 

1.  문자열을 기준으로 알파벳을 앞으로 이동 or 뒤로 이동 => 더 짧은 방법으로 이동

    -> 그럼 앞으로 이동하는 배열과 뒤로 이동하는 배열을 만들어야겠다! 

         ([a,b,c...z],[z,y,x......])

2. 그리고 A가 나오면 더이상 이동할 필요없는 것을 구현해야겠다.

     -> 양방향 어디로 이동하던지 마지막까지 이동했을 때의 값이 A가 아니라면 무조건 마지막까지 이동해야함

          만약 A다음으로 이동할 때 쭉 A만 나온다면 A나오기 전에 이동을 끝낼 수가 있음

          앞으로 이동했을 때의 A의 개수와 뒤로 이동했을 때의 A의 연속 개수를 세야겠다~!

          ex. AAABABAAC =>뒤로 이동시 마지막이 C이기 때문에 끝까지 이동해야하지만 앞으로 이동시에 B까지만 이동하면 됨

          그럼 순서대로 문자열과 거꾸로 문자열을 두 개로 나눠 A가 연속되는 갯수를 세고(연속 끝나면 브레이크) A가 더 적은 것의 이동 수를 센다..

 

정답 나온 다른사람 풀이

def solution(name):
    answer = 0
    min_move = len(name) - 1
    
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), 26 - (ord(char) - ord('A')))
        
        next_i = i + 1
        while next_i < len(name) and name[next_i] == 'A':
            next_i += 1
            
        move_forward = i + i + len(name) - next_i
        move_backward = (len(name) - next_i) * 2 + i
        min_move = min(min_move, move_forward, move_backward)
    
    answer += min_move
    return answer

수정 중..