조이스틱

 

코딩테스트 연습 - 조이스틱 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이

def cleck_ct(alpa_name):
    alpa = {'A':0, 'B':1, 'C':2, 'D':3, 'E':4, 'F':5,
            'G':6, 'H':7, 'I':8, 'J':9, 'K':10, 'L':11,
            'M':12, 'N':13, 'O':14, 'P':15, 'Q':16, 'R':17,
            'S':18, 'T':19, 'U':20, 'V':21, 'W':22, 'X':23,
            'Y':24, 'Z':25}
    return min(alpa[alpa_name], 26-alpa[alpa_name])

def solution(name):
    answer = 0
    lenth_name = len(name)
    name_idx = []
    for i in range(len(name)):
        answer+=cleck_ct(name[i])
        if name[i]!='A':
            name_idx.append(i)
    
    if not name_idx:
        return answer
    
    max_lenth = name_idx[-1]
    for idx in range(len(name_idx)-1):
        now_idx = name_idx[idx]
        next_idx = name_idx[idx+1]
        if (now_idx+1)!=(next_idx):

            # 오른쪽 ㄱㄱ 왼쪽
            max_lenth = min(max_lenth, (now_idx*2)+lenth_name-next_idx)
            # 왼쪽 ㄱㄱ 오른쪽
            max_lenth = min(max_lenth, (lenth_name-next_idx)*2+now_idx)

    return answer+max_lenth

 

 

시간 복잡도

for i in range(len(name)) : name을 순회하므로 선형시간
     cleck_ct : 내부 딕셔너리 상수시간

for idx in range(len(name_idx)-1) : 'A'가 아닌 문자열 인덱스 리스트(name_idx)를 순회하므로 선형시간
즉, 시간 복잡도는 선형 시간복잡도( O(n) )