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

문제 링크

풀이

그리디의 탈을 쓴 브루트포스

원랜 그리디로 풀렸던 거 같은데 22년에 테케가 추가된 이후로는 그리디로 안 풀린다는 질문글이 폭주하고 있다. 원래 그리디는 현재 상황에서 최적의 해를 탐색해나가는 방식인데, 이 문제는 그렇게 풀리지 않는다. 모든 상황을 다 탐색하고 최적의 해를 찾아내야 하는 완전 탐색 문제로 변질(?)되었다. 그리디에 꽂혀서 열심히 풀었는데.. ㅎ

아래는 반례

"BBBAAAAAAAB"

8

❌ 그리디(Greedy, 탐욕법) 풀이

현재 위치에서 가장 가까운 A가 아닌 문자를 찾아서 그때그때 판별하고 탐색하는 방식. 그리디라고 생각했는데 완전한 그리디 코드는 아닌 것 같다.

def control(s):
    return min(ord(s)-65, 91-ord(s))

def solution(name):
    answer = 0
    
    name = list(name)
    idx, L = 0, len(name)
    while set(name) != {'A'}:
        left = right = 0
        while True:
            
            if name[(idx+right)%L] != 'A':
                idx = (idx+right)%L
                answer += right
                break
                
            if name[(idx+left)%L] != 'A':
                idx = (idx+left)%L
                answer -= left
                break
            
            left -= 1
            right += 1
        
        answer += control(name[idx])
        name[idx] = 'A'
        
    return answer

⭕️ 완전탐색

BFS 방식으로 풀었다. 단 여기서는 해답을 찾는다고 곧바로 최적해가 나오는 것은 아니다. 바꿔야 하는 단어가 4개라면, 4개를 찾을 수 있는 여러개의 과정이 있고 그 과정들을 전부 비교해야 한다.

만약 바꿔야 하는 문자가 3개라면, 어떤 방식으로 하든 3번의 과정만 거치면 전부다 정답이 되어있다. 여기선 똑같은 목표를 향해 가되, 얼마나 걸리는가의 문제이며, 그 과정이 한단계 씩 이루어지는 게 아니라 문자 단위로 이루어지기 때문이다. 3번의 과정을 거치면 큐에서 모든 값을 꺼내서 비교하면서 가장 적게 걸린 값을 찾는다.

def control(s):
    return min(ord(s)-65, 91-ord(s))

def solution(name):
    name = list(name)
    
    L = len(name)
    d = control(name[0])
    name[0] = "A"
    queue = deque([(name, d, 0)])
    while queue:
        _name, d, idx = queue.popleft()
        
        # 현재부터 뒤에 있는 모든 값을 다 비교해서 
        # 가장 작은 d를 찾는다. 
        if _name == ['A']*L:
            answer = d
            while queue and queue[0][0] == ['A']*L:
                answer = min(answer, queue.pop()[1])
            return answer
        
        # 왼쪽으로 이동했을 때
        left = -1
        while _name[(idx+left)%L] == 'A':
            left -= 1

        left_name, next = _name[:], (idx+left)%L
        _d = d - left + control(_name[next])
        left_name[next] = 'A'
        queue.append((left_name, _d, next))
        
        # 오른쪽으로 이동했을 때
        right = 1
        while _name[(idx+right)%L] == 'A':
            right += 1
        
        right_name, next = _name[:], (idx+right)%L
        _d = d + right + control(_name[next])
        right_name[next] = 'A'
        queue.append((right_name, _d, next))

from collections import deque

테케가 무려 27개!
그리디이던 시절에는 10개였던듯