[알고리즘] 프로그래머스 - 조이스틱

조이스틱

---

문제 설명

게임 캐릭터의 이름을 원하는 대로 바꾸기 위해,
현재 화면에 표시된 모든 문자가 "A"인 상태에서 목표 이름으로 바꾸려 합니다.
조이스틱은 아래의 두 가지 동작을 수행할 수 있습니다.

• 상하 이동: 현재 선택된 문자를 위나 아래로 변경하여 원하는 알파벳으로 만듭니다.
  • 예를 들어, "A"에서 "B"로 갈 때는 한 번 이동, "A"에서 "Z"로 갈 땐 한 번 이동 (역방향)
• 좌우 이동: 커서를 왼쪽 혹은 오른쪽으로 이동하여 다른 문자를 선택합니다.
  • 커서는 문자열의 양 끝을 연결하여 원형으로 움직입니다.

목표는 이 두 가지 조작을 사용해,
최소한의 조이스틱 조작으로 목표 이름을 완성하는 것입니다.

제한 조건

• name: 길이가 1 이상 20 이하인 대문자 문자열
  • (예: "JEROEN", "JAN" 등)

내가 접근한 방법

---

1. 문자 변경 최소 연산 계산

• 각 문자를 "A"에서 목표 알파벳으로 변경할 때,
  • 상하 이동으로 필요한 최소 연산 수를 계산합니다.
• 알파벳의 순서를 양방향(위, 아래)에서 접근하여 더 적은 이동 횟수를 선택합니다.
  • 예를 들어, "A"에서 "N"(중간값)까지 갈 경우, 양쪽 방향의 이동 횟수가 달라질 수 있습니다.

2. 커서 좌우 이동 최소 거리 계산

• 문자를 변경한 후, 커서 이동을 통해 다음 변경 대상 문자로 이동합니다.
• 좌우 이동 과정에서 연속된 "A" 문자가 있을 경우,
  • 이를 건너뛰어 좌우 이동을 최소화하는 전략을 사용합니다.
• 모든 위치에 대해, 오른쪽으로 간 후 다시 돌아오는 경우와, 왼쪽에서 오른쪽으로 접근하는 경우를 각각 고려하여 최소 이동 횟수를 산출합니다.

3. 최종 연산 수 계산

• 각 문자별 변경 연산 수와, 전체 커서 이동 최소 횟수를 합산하여
  문제에서 요구하는 최소 조작 횟수를 구합니다.

import Foundation

func solution(_ name:String) -> Int {
    // 각 문자를 목표 문자로 바꾸는 데 필요한 최소 상하 이동 횟수를 계산.
    let changeDistance: Int = name
        .map { char in
            let asciiValue = Int(char.asciiValue!)
            // 'A'(65)부터 'Z'(90)까지, 중간값 'N'(78) 근처를 기준으로 최소 이동값 계산
            return asciiValue <= 77 ? asciiValue - 65 : 90 - asciiValue + 1
        }
        .reduce(0, +)
    
    // 기본 커서 이동은 끝까지 전진하는 것으로 초기값 설정.
    var move = name.count - 1
    for i in 0..<name.count {
        var next = i + 1
        // 연속된 'A'를 건너뛰도록 next 값을 증가
        while next < name.count && Array(name)[next] == "A" {
            next += 1
        }
        
        // 오른쪽으로 갔다가 돌아오는 경우
        let rightThenLeft = i + i + (name.count - next)
        // 왼쪽으로 갔다가 오른쪽으로 돌아오는 경우
        let leftThenRight = (name.count - next) + (name.count - next) + i

        // 가능한 경우 중 최소 이동 횟수를 선택
        move = min(move, rightThenLeft, leftThenRight)
    }
    
    // 문자 변경과 커서 이동의 총 연산 수를 반환
    return changeDistance + move
}

정리

• 상하 이동 최적화:
  각 문자를 바꾸기 위해, 직접 아래나 위로 이동하는 두 방향 중 더 적은 횟수를 선택합니다.
• 좌우 이동 최적화:
  연속된 "A" 문자를 효과적으로 건너뛰며, 커서를 이동하는 경로를 여러 방식(오른쪽 먼저, 왼쪽 먼저)으로 고려합니다.
• 결과:
  두 가지 최적화 전략(문자 변경, 커서 이동)을 합산하여 문제에서 요구하는 최소 조작 횟수를 계산합니다.