프로그래머스 greedy 문제 조이스틱 파이썬 풀이/코드 (LV2..이긴한데 LV2맞나)

문제설명 ㄱ

코딩테스트 연습 - 조이스틱

간단히 얘기하자면, 예를들어, AAA라는 문자열이 있으면 이걸 JAZ 라는 주어진 문자열로 바꾼다고 생각하자. 그 과정의 모든 동작을 카운트하는데  시작은 맨 왼쪽 0번째 문자열인데, A를 J까지 바꾸는데 총 9번의 순서가 소요된다. 그리고 이제 왼쪽 문자열(-1째 문자열)로 넘어가는데 한번의 순서가 소요되고 A -> Z까지 갈 때에는 정 순서보다 역순서가 더 빠르니까 역순서로 ..순서를 카운트해서 또 한번을 추가한다. 이렇게 하면 총 11번만의 조작으로 AAA를 JAZ로 바꿀 수 있다. 

 

다시 얘기하면 결국 A에서 어떤 다른 문자로 넘길때 소요되는 조이스틱 사용횟수(상하) +

문자열을 오른쪽으로 훑을지, 왼쪽으로 훑을지, 왼쪽으로 갔다가 AAAAA문자열을 만나서 다시 오른쪽으로 돌아가서 나머지 부분을 처리할지를 확인해야한다. 저렇게 긴 문자열로 된 AAAAAAA가 있으면 이부분을 차라리 안 훑고 되돌아가서 뒷쪽부터 다시 세는게 더 값이 잘 맞을 수도 있으니까.(좌우)

 

상하는 너무 쉬워서, 좌우가 문제인 문제인데.. 종일 이문제만 붙잡고 있었는데 훌륭한 풀이를 찾아서 (맨위에꺼 잘 안 클릭하는 경향이 있어서 가장 마지막에 봤는데 이풀이가 가장 직관적이고 마음에 들었다 ...띠밤(내가참고한..링크)

[프로그래머스, 파이썬] 조이스틱, Greedy

요건 내 풀이(거의똑같..)

def solution(name):
    answer = 0
    
    num_list = [min(abs(ord('A')-ord(n)), 26-abs(ord('A')-ord(n))) for n in name]
    #상하로 갯수 미리 세서 걍 다 더해놓기.
    answer += sum(num_list)
    min_move = len(name) - 1
    
    for i, c in enumerate(name):
        
        next_i = i+1
        
        while next_i < len(name) and name[next_i] == 'A':
            next_i += 1
        # 각 문자부터 'A..'문자가 있을경우 몇번씩 조이스틱쓰는지 체크
        min_move = min(min_move, 2*i+ len(name)-next_i, 2*(len(name)-next_i)+i)
    
    return answer+min_move

 

여기에서 푼 방법은, 각 문자별로 해당 문자부터 긴- A 문자열이 있는지 확인하고 만약 있다면 그 문자열을 기준으로 오른쪽부터 왓다가.. 백해서 다시 뒤로 가는 경우랑 왼쪽으로(거꾸로) 먼저 탐색 후 뒤돌아와서 탐색하는 경우랑 기본(length-1)을 비교해서 그중에 가장 작은 값을 저장하는 방식이다. 왼쪽먼저탐색/오른쪽먼저탐색/일반 이렇게 세개를 비교한다고 보면 된다.

 

 

왼쪽/오른쪽 먼저 탐색여부가 왜 중요하냐면, 먼저 탐색햇다가 백하면 *2를 해야하니까 .. 그게 상당히 중요해진다. 이 풀이가 가~장 좋았다(내기준)

 

 

솔직히 이거 그리디아님..그리디로 풀면 답안나와,, 그리디로 하더라도 왼쪽먼저/오른쪽 먼저 ..로 해서 각각 의 경우에 대해서 다시 또 왼쪽/오른쪽 계산해야될..거같다.