[프로그래머스lv.2] 조이스틱

[정답코드]

from collections import deque
import copy
def solution(name):
    answer = float("inf")
    name = list(name)
    
    origin=['A']*len(name)
    
    now = 0
    
    controll=0
    controll+=min(ord(name[now])-ord('A'), ord('Z')-ord(name[now])+1)#min(ord(name[now])-65, 90-ord(name[now])+1)
    
    origin[now]=name[now]
    q=deque([])
    q.append((now, controll, origin))
    while q:
        now, controll, origin =q.popleft()
        if origin == name:
            answer=min(answer, controll)
            continue

        check=0
        rcontroll = controll
        rnow=now
        while check<1:
            # 오른쪽으로 가는 경우, 
            rnow=rnow+1
            if rnow>=len(name):
                rnow=0
            # 값을 바꿀 필요가 있는 경우 
            if origin[rnow]!=name[rnow]:
                if 0<=rnow<len(name):
                    check=1
                    rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1

                    break
                    #q.append((nnow, controll+1, origin))
            # 값을 바꿀 필요가 없는 경우 
            else:
                rcontroll+=1

        check = 0
        lcontroll = controll
        lnow=now
        while check<1:
            # 왼쪽으로 가는 경우,     
            lnow = lnow -1
            if lnow<0:
                lnow=len(name)-1
            # 값을 바꿀 필요가 있는 경우
            if origin[lnow]!=name[lnow]:
                if 0<=lnow<len(name) :
                    check = 1  
                    lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
                    break
            else:
                lcontroll+=1

        originl=origin[:]
        originr=origin[:]
        originl[lnow]=name[lnow]
        q.append((lnow, lcontroll, originl))
        originr[rnow]=name[rnow]
        q.append((rnow, rcontroll, originr))
            
    
    return answer

 

 

일단 이 문제는 그리디 문제이긴 한데, 그리디 하지 않다. 

 

from collections import deque
import copy
def solution(name):
    answer = float("inf")
    name = list(name)
    origin=['A']*len(name)
    now = 0
    controll=0
    controll+=min(ord(name[now])-65, 90-ord(name[now])+1)
    origin[now]=name[now]
    q=deque([])
    q.append((now, controll, origin))
    while q:
        # print('!', now, controll, origin)
        now, controll, origin =q.popleft()
        
        if origin == name:
            
            answer=min(answer, controll)
            #print('answer', answer)
            continue

        check=0
        rcontroll = controll
        rnow=now
        while check<1:
            # 오른쪽으로 가는 경우, 
            rnow=rnow+1
            if rnow>=len(name):
                rnow=0
            
            # 값을 바꿀 필요가 있는 경우 
            if origin[rnow]!=name[rnow]:
                if 0<=rnow<len(name):
                    check=1
                    # print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
                    rcontroll+=min(ord(name[rnow])-65, 90-ord(name[rnow])+1)+1
                    #origin[rnow]=name[rnow]
                    break
                    #q.append((nnow, controll+1, origin))
            # 값을 바꿀 필요가 없는 경우 
            else:
                rcontroll+=1

        check = 0
        lcontroll = controll
        lnow=now
        # print('lnow1',lnow)
        while check<1:
            # 왼쪽으로 가는 경우,     
            lnow = lnow -1
            if lnow<0:
                lnow=len(name)-1
            # 값을 바꿀 필요가 있는 경우
            if origin[lnow]!=name[lnow]:
                if 0<=lnow<len(name) :
                    check = 1
                    # print('now controll', controll, 'plus', min(ord(name[nnow])-65, 90-ord(name[nnow])))
                    lcontroll+=min(ord(name[lnow])-65, 90-ord(name[lnow])+1)+1
                    #origin[lnow]=name[lnow]
                    break
                    #q.append((nnow, controll+1, origin))
            else:
                lcontroll+=1
        # print('lnow2',lnow)
        #print('lcontroll, rcontroll:', lcontroll-controll, rcontroll-controll, ',', lcontroll, rcontroll,'controll', controll)      
        if lcontroll<rcontroll:
            #print('hi', origin)
            origin[lnow]=name[lnow]
            #print('hi2', origin, 'lcontroll',lcontroll)
            q.append((lnow, lcontroll, copy.deepcopy(origin)))
        elif lcontroll>rcontroll:
            #print('hi', origin)
            origin[rnow]=name[rnow]
            
            #print('hi2', origin, 'lcontroll',lcontroll)
            q.append((rnow, rcontroll, copy.deepcopy(origin)))
        else:
            originl=copy.deepcopy(origin)
            originr=copy.deepcopy(origin)
            originl[lnow]=name[lnow]
            q.append((lnow, lcontroll, copy.deepcopy(originl)))
            originr[rnow]=name[rnow]
            q.append((rnow, rcontroll, copy.deepcopy(originr)))
            
        
    # print(controll)
    
    
    return answer

 

 

이렇게 작성한 코드에서

이런식으로 도저히 넘어가질 않았음.

그런데 내가 하루종일 찾은 테스트케이스는 모두 통과되는 상태임.

 

이건 진짜 근본적인 문제가 하나 있다 싶었다. 

 

내가 이 문제를 풀기위해 사용한 핵심 로직은 

 

"지금 당장 더 싼 쪽(왼쪽 vs. 오른쪽)만 골라서 다른 쪽은 아예 버린다"
(만약 두쪽 다 값이 같으면 둘다 살려줌)

 

이였고, 오히려 그리디한 그리디 분기(pruning) 로직임.

그런데 이게 문제를 해결할 수 없는 결정적인 오류였음. 

이렇게 하면, 현재 상황에서 비용이 더 큰 쪽 경로를 전혀 탐색하지 않는데, 이 경우에서 만약 나중에 더 긴 A 구간이 나와버리면,  “한 번에 건너뛰어서” 전체 이동 횟수를 줄여 줄 수도 있는 상황을 전부 잘라 버림. 

결과적으로, 단편적인 부분에서 싸 보인다고 더 비싼 쪽 경로를 잘라 버리는 순간, 전역 최적해를 놓치게 되는거임;

 

결국 더 싼쪽 골라서 q에 넣기보다는 아예 저 조건 싹 지워버렸음

폭포수 시원하게 흐르는 것 같노

 

 

 

느낀점 : 그리디 문제도 깊게 생각할 부분이 있구나 하는것을 알게되었음.