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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42860#

프로그래머스

 

이게 왜 Level 2이지? 알 수가 없다

 

---

 

주요 아이디어

• Greedy 문제 유형에 나와있어서, 한 글자마다 최적의 선택을 하면 solution을 보장하는 문제라고 생각했다
• 상하 이동은 그냥 target이 A에 가까운지 Z에 가까운지에 따라 결정
• 좌우 이동이 중요하다
  • 예시
    AAAAN
    
    바꿔야 될 position 선택
    ->: 4
    <-: 1
    즉 타깃이 되지 못한 알파벳이 좌우로 몇 개 남았는지에 따라서 좌우 결정

 

• 현재 문자열을 앞에 덧붙여서 만든다
  • ex. JEREON -> EROENJEREON
• 처음은 중간 위치 (len(str) // 2) 에서 시작
• 매 위치마다 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리를 체크한 이후, 알파벳을 변경하고 이동을 진행한다

 

 

 

---

 

코드 구현 (Python 3)

 

def up_down(alpha):
    return min(abs(ord('Z') - ord(alpha) + 1), abs(ord(alpha) - ord('A')))

# 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리
def go_left(name, target, idx):
    # left
    left_cnt = 0
    for i in range(idx, 0, -1):
        if name[i] == target[i]:
            left_cnt += 1
        else:
            break
    # right
    right_cnt = 0
    for i in range(idx, len(target)):
        if name[i] == target[i]:
            right_cnt += 1
        else:
            break
    
    if left_cnt < right_cnt:
        return True
    else:
        return False

def solution(target):
    target = target[1:] + target
    print(target)
    answer = 0
    
    target = [x for x in target]
    name = ["A" for _ in range(len(target))]
    
    p = len(target) // 2 # 처음 시작 인덱스 (중간)
    
    while name != target:
        if name[p] != target[p]:
            # 해당 자리에서 변경
            answer += up_down(target[p])
            # 현재 인덱스 + len(str) // 2 + 1
            # 현재 인덱스가 가운데 기준 왼쪽일 경우
            if p < len(target) // 2:
                name[p] = target[p]
                name[p + len(target)//2 + 1] = target[p]

            # 현재 인덱스가 가운데 기준 오른쪽일 경우
            # 현재 인덱스 - len(str) //2 -1 
            elif p > len(target) // 2:
                name[p] = target[p]
                name[p - len(target)//2 - 1] = target[p]

            # 현재 인덱스가 가운데
            else:
                name[p] = target[p]
                
			# 변경 후 
            if name == target:
                break
                
        # 왼쪽 이동
        if go_left(name, target, p):
            p -= 1
            answer += 1
        else:
            p += 1
            answer += 1
            
    return answer

 

 

 

처음엔 깔끔히 통과한 줄 알았으나..

일부 테스트 케이스에서 실패가 떴다.

 

 

코드 재구현 (Python 3)

이동 개수가 같을 때 방향에 따라서도 값이 달라지나 싶어서 다시 코드를 수정해봤다.

def up_down(alpha):
    return min(abs(ord('Z') - ord(alpha) + 1), abs(ord(alpha) - ord('A')))

# 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리
def go_left(name, target, idx, direction):
    # left
    left_cnt = 0
    for i in range(idx, 0, -1):
        if name[i] == target[i]:
            left_cnt += 1
        else:
            break
    # right
    right_cnt = 0
    for i in range(idx, len(target)):
        if name[i] == target[i]:
            right_cnt += 1
        else:
            break
    
    print(f"## left cnt : {left_cnt} right cnt : {right_cnt}")
    if left_cnt < right_cnt:
        return True
    elif left_cnt > right_cnt:
        return False
    else:
        if direction == "left":
            return True
        else:
            return False

def solution(target):
    target = target[1:] + target
    target = [x for x in target]
    
    p = len(target) // 2 # 처음 시작 인덱스 (중간)
    
    left_first = 0; right_first = 0

    left_name = ["A" for _ in range(len(target))]
    right_name = ["A" for _ in range(len(target))]


    while left_name != target:
        print(target[p], left_name[p])
        print(up_down(target[p]))
        if left_name[p] != target[p]:
            # 해당 자리에서 변경
            left_first += up_down(target[p])
            # 현재 인덱스 + len(str) // 2 + 1
            # 현재 인덱스가 가운데 기준 왼쪽일 경우
            if p < len(target) // 2:
                left_name[p] = target[p]
                left_name[p + len(target)//2 + 1] = target[p]

            # 현재 인덱스가 가운데 기준 오른쪽일 경우
            # 현재 인덱스 - len(str) //2 -1 
            elif p > len(target) // 2:
                left_name[p] = target[p]
                left_name[p - len(target)//2 - 1] = target[p]

            # 현재 인덱스가 가운데
            else:
                left_name[p] = target[p]

            print("변경된 문자열 : ", left_name)
            if left_name == target:
                break
        
        if go_left(left_name, target, p, "left"):
            p -= 1
            left_first += 1
            print("move left")
        else:
            p += 1
            left_first += 1
            print("move right")
    
    print('#' * 10)

    p = len(target) // 2 # 처음 시작 인덱스 (중간)
    
    while right_name != target:
        print(target[p], right_name[p])
        print(up_down(target[p]))
        if right_name[p] != target[p]:
            # 해당 자리에서 변경
            right_first += up_down(target[p])
            # 현재 인덱스 + len(str) // 2 + 1
            # 현재 인덱스가 가운데 기준 왼쪽일 경우
            if p < len(target) // 2:
                right_name[p] = target[p]
                right_name[p + len(target)//2 + 1] = target[p]

            # 현재 인덱스가 가운데 기준 오른쪽일 경우
            # 현재 인덱스 - len(str) //2 -1 
            elif p > len(target) // 2:
                right_name[p] = target[p]
                right_name[p - len(target)//2 - 1] = target[p]

            # 현재 인덱스가 가운데
            else:
                right_name[p] = target[p]

            print("변경된 문자열 : ", right_name)
            if right_name == target:
                break
        
        if go_left(right_name, target, p, "right"):
            p -= 1
            right_first += 1
            print("move left")
        else:
            p += 1
            right_first += 1
            print("move right")
    
    # print(left_first, right_first)
    return min(left_first, right_first)

스파게티 코드

 

다 맞은 줄.. 알았는데..??

결과는 실패..

 

 

 

---

 

실패 원인

이번에도 책을 참고해서 원인을 살펴보았다.

 

반례

"BBABAAAB"

내가 짠 로직

그런데.. 이것보다 더 적은 횟수로 변경할 수 있는 방법이 있다!

 

바로 왔던 길을 "되돌아가는" 경우다.

 

일반적인 경우라면 놓치기 쉽지만, 이렇게 A가 연달아 길게 있는 경우, 그대로 이동하는 것보다 되돌아가는 것이 더 횟수를 줄일 수 있다.

 

반례 찾기 참 힘들다

 

따라서 커서는 "연속된 A 문자열을 최대한 피해서" 이동해야 한다.

 

 

---

 

코드 재구현 (Python 3)

def up_down(target):
    return min(abs(ord(target) - ord('A')), abs(ord('Z') - ord(target) + 1))

def solution(name):
    # 알파벳 변경 횟수, 커서 변경 횟수
    spell_move = 0; cursor_move = len(name) - 1 # 최대 이동 거리

    for idx, ch in enumerate(name):
        # 상하이동부터
        spell_move += up_down(ch)

        # 해당 인덱스 다음부터 연속된 A 문자열 찾기
        next_idx = idx + 1
        while next_idx < len(name) and name[next_idx] == 'A':
            next_idx += 1
        
        # next_idx : 연속된 A 문자열의 오른쪽 끝 인덱스
        # 왼쪽 순회 거리, 오른쪽 순회 거리 중 최소값 비교
        distance = min(idx, len(name) - next_idx)
        
        # 실제 이동 거리 계산 (순방향 VS 역방향 거리 계산)
        cursor_move = min(cursor_move, idx + len(name) - next_idx + distance)

    answer = spell_move + cursor_move
    
    return answer

 

---

 

제출 결과