1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def solution(name):
    """
    # greedy하게 이동할 곳을 탐색 (알파벳을 바꿀 인덱스 중 가장 가까운 인덱스)
    name = list(name)
    def greedyFind(name, start):
        indexes = []
        for i in range(len(name)):
            if name[i] != 'A':
                indexes.append(i)
        res = [ (i, min([(len(name)-start+i)%len(name), (len(name)+start-i)%len(name)])) for i in indexes ]
        return sorted(res, key=lambda x: x[1])[0]
    answer = 0
    start = 0
    while ''.join(name) != 'A'*len(name):
        start, distance = greedyFind(name, start)
        answer = answer + distance + min(ord(name[start])-ord('A'), 26+ord('A')-ord(name[start]))
        name[start] = 'A'
        print(name, answer)
    return answer
    """

    import itertools
    indexes = [ i for i, c in enumerate(name) if c != 'A' ]

    # dictionary for distances
    d_distance = {}
    for i in set([0]+indexes):
        for j in set([0]+indexes):
            d_distance[f"{i}_{j}"] = min([(len(name)-i+j)%len(name), (len(name)+i-j)%len(name)])

    # dictionary for switching costs 
    d_switch = {}
    for i in set([name[i] for i in indexes]):
        d_switch[i] = min(ord(i)-ord('A'), 26+ord('A')-ord(i))

    answer = float('inf')
    res_switch = sum([d_switch[name[i]] for i in indexes])
    for case in itertools.permutations(indexes):
        res = res_switch
        start = 0
        for i in case:
            res = res + d_distance[f"{start}_{i}"]
            start = i
        answer = min(answer, res)
    return answer