[programmers] 조이스틱_greedy

[코딩테스트 연습] 조이스틱

link

풀이

• 방식 : Greedy
• 두 가지로 구분하여 문제를 접근, Cursor의 이동과 알파벳 변경
• 변수 s에 알파벳 변경에 필요한 조이스틱 조작 횟수
• 변수 c는 Cursor 이동 횟수
• 문자열을 뒤로 하나 씩 보내고 Left Strip을 통해 ‘A’를 지운 문자열의 길이에 이동하는데 필요한 a만큼 더 해줌

📰code

def solution(name):
    s = sum(list(map(lambda x : min(ord(x)-ord('A'),ord('Z')+1-ord(x)), name)))
    c = len(name)
    a = 0
    for i in range(len(name)//2+1):
        if i>=1:
            a =  len(name[:i])-1
        c = min(c,len((name[i:] + name[:i]).lstrip('A'))+a)
    return s+c-1

다른 풀이

• 위와 같은 방식으로도 통과가 가능하지만, 예외 문자열이 있음
• name을 “BBABAAAB”로 입력 시 [왼 오 오 오 오]에 대한 경우 확인이 어려움
• 이 부분을 보완하기 위해 왼쪽으로 시작하는 것 뿐만 아니라, 오른쪽으로 시작하는 것을 추가함

📰code

def solution(name):
    
    s = sum(list(map(lambda x : min(ord(x)-ord('A'),ord('Z')+1-ord(x)), name)))
    c_r, c_l = len(name), len(name)
    a_r, a_l = 0, 0
    
    for i in range(len(name)//2+1):
        if i>=1:
            a_r =  len(name[:i])-1
            a_l =  len(name[-i:])
        c_r = min(c_r,len((name[i:] + name[:i]).lstrip('A'))+a_r)
        c_l = min(c_l,len((name[-i:] + name[:-i]).rstrip('A'))+a_l)
        
    c = min(c_r,c_l)
    
    return s+c-1

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡