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

🚫 처음 풀이

이 문제가 유형이 그리디로 분류되어 있어서 처음에는 그리디로 풀기 위해 노력을 했습니다. 일종의 시뮬레이션 코드를 만들어놓고 현재 cursor의 위치에서 가장 A가 아닌 글자로 이동하는 것을 반복하는 식으로 문제를 해결하려고 했습니다. 하지만 일부 테스트 케이스만 통과할 수 있었습니다.

extension Character {
    var control: Int {
        let up = Int(self.asciiValue!) - Int(Character("A").asciiValue!)
        let down = Int(Character("Z").asciiValue!) - Int(self.asciiValue!) + 1
        return up < down ? up : down
    }
}

func solution(_ name:String) -> Int {
    func findNextR() -> (Int, Int) {
        var now = cursor
        var count = 0
        while true {
            now = (now + 1) % name.count
            count += 1
            if !check[now] { return (now, count) }
        }
    }
    
    func findNextL() -> (Int, Int) {
        var now = cursor
        var count = 0
        while true {
            now = (now - 1) > 0 ? now - 1 : name.count - 1
            count += 1
            if !check[now] { return (now, count) }
        }
    }
    
    let controls = name.map { $0.control }
    var check = Array(repeating: false, count: name.count)
    for i in 0..<controls.count {
        if controls[i] == 0 { check[i] = true }
    }
    
    var result = controls.reduce(0, +)
    print("알파벳 초기 비용: \(result)")
    var cursor = 0
    check[cursor] = true
    
    while check.filter({ $0 == false }).count != 0 {
        let nextR = findNextR()
        let nextL = findNextL()
        
        if nextR.1 < nextL.1 {
            cursor = nextR.0
            result += nextR.1
            check[cursor] = true
            print("현재 cursor: \(cursor), 처리한 알파벳: \(name.map{$0}[cursor]), 이동비용: \(nextR.1), 총비용: \(result)")
        } else if nextR.1 >= nextL.1  {
            cursor = nextL.0
            result += nextL.1
            check[cursor] = true
            print("현재 cursor: \(cursor), 처리한 알파벳: \(name.map{$0}[cursor]), 이동비용: \(nextL.1), 총비용: \(result)")
        }
    }
    
    return result
}

참고한 블로그 🙏

이 블로그에서 풀이법의 실마리를 얻었습니다. 감사합니다!

[알고리즘 연습] 조이스틱 (프로그래머스 lv2, 스위프트)

문제 풀이 아이디어

일단 이 문제는 그리디는 아닙니다. 오히려 브루탈 포스에 가까운 문제라고 봐야할 것 같습니다. 일단 상하 조이스틱의 조작 횟수는 정해져있으니 (위로 올라가는 조작 vs 아래로 내려가는 조작 중에 최솟값) 크게 신경쓸 필요는 없습니다. extension으로 구현한 것을 그대로 가져다가 쓰겠습니다.

좌우 이동의 3가지 케이스

우리가 신경써야 하는 것은 좌우 이동입니다. 좌우 이동에는 아래 3가지 케이스가 있습니다.

1. “우" 버튼만을 이용해서 오른쪽으로 쭉 이동하는 경우 (시작 지점 ~ A가 아닌 마지막 글자)
2. “우" 버튼을 이용해서 A가 아닌 글자까지 조작한 후 “좌" 버튼으로 다시 돌아가서 맨뒤 지점해서 A가 아닌 글자까지 이동하는 경우
3. “좌” 버튼을 이용해서 일단 맨뒤로 이동해서 A가 아닌 글자까지 조작한 후 “우" 버튼으로 다시 처음으로 돌아와서 A가 아닌 글자까지 이동하는 경우

1번의 경우 아주 간단합니다. 그냥 글자가 쓰여진 순서대로 이동하는 것이죠. 조작 횟수는 A가 아닌 마지막 글자의 index가 될 것입니다.

하지만 2와 3의 경우가 특수한 케이스입니다. 1번의 일직선 이동보다 돌아가는 2와 3의 케이스가 더 나은 경우는 A가 아닌 두 글자 사이에 A가 많이 위치한 경우 입니다. 조작할 필요가 없는 A를 가로질러 가는 것 보다는 차라리 뒤로 돌아서 이동하는 것이 더 빠른 경우이죠

예시

BCAAAEAD

위 예시를 한번 봅시다. 1번으로 이동하는 경우 중간에 A 3개를 건너뛰어야 하므로 최소 루트가 아닙니다. 2번 루트의 경우 C까지 일단 이동을 하고 뒤로 돌아서 E까지 이동하면 됩니다. 반면에 3번의 경우 뒤로 돌아가서 E까지 이동하고 다시 돌아서 C까지 오면 됩니다. 2 혹은 3이 최솟값이 될텐데 이 예시의 경우 2번 루트가 최솟값입니다. 3번 루트는 E와 D 사이에 있는 A를 두번 지나가게 되므로 동선의 낭비가 발생하기 때문입니다.

BACAAAED

이번에는 다른 예시를 한번 보겠습니다. 1번의 경우 같은 이유로 최소 루트가 아닙니다. 2번의 경우 일단 C까지 이동하고 뒤로 돌아서 E까지 이동합니다. 3번의 경우 E까지 이동하고 C까지 이동하는 루트입니다. 이번에는 3번 루트가 최소 동선입니다. 2번의 경우 B와 C 사이의 A를 두번 지나가기 때문입니다.

뒤로 도는 지점을 찾아라!

2번 루트와 3번 루트의 길이를 측정하는 것은 아주 쉽습니다. 돌아가는 지점까지의 거리에 2를 곱해주면 원 위치로 오고 거기에 다른 지점까지의 거리를 더해주면 됩니다.

// 위 2가지 예시에서 각 루트별 길이 계산
let (2번 루트의 길이) = (B에서 C까지 거리) * 2 + (B에서 E까지의 거리)
let (3번 루트의 길이) = (B에서 E까지의 거리) * 2 + (B에서 C까지 거리)

하지만 문제는 C와 E 지점 (= 다수의 A 사이의 양끝 지점)을 어떻게 찾을 것인지 입니다. 이 두 지점을 찾기 위해서 브루탈 포스를 사용합니다.

코드

아래 코드에서 left가 예시의 C이고 right가 예시의 E라고 보고 이해하시면 됩니다.

import Foundation

extension Character {
    // 해당 문자를 만들기 위해서 조작해야 하는 up 또는 down 버튼의 최소 조작횟수
    var updown: Int {
        let up = Int(self.asciiValue!) - Int(Character("A").asciiValue!)
        let down = Int(Character("Z").asciiValue!) - Int(self.asciiValue!) + 1
        return up < down ? up : down
    }
}

func solution(_ name:String) -> Int {
    // 모든 문자를 updown 조작 회수로 바꾼다
    let updownArray = Array(name).map { $0.updown }

    // 문자를 변경하는 조작 횟수 (모든 updown 횟수를 더한다.)
    let totalUpdown = updownArray.reduce(0, +)
    
    // 좌우 조작의 기본값은 그냥 첫 글자에서 마지막 A가 아닌 글자까지 일직선으로 (right 버튼만 사용해서) 이동하는 경우
        // 만약에 name[0]을 제외한 모든 글자가 0이라면 값은 0이 된다.
    var leftright = updownArray.lastIndex { $0 != 0 } ?? 0

    //✅ 좌우조작을 할 때 돌아가는 케이스에 대한 예외 처리 (= 맨처음에서 좌로 이동해서 맨뒤로 가는 케이스)
        // 어떤 두 글자 사이에 A가 많이 있으면 차라리 돌아가는게 낫다.
            // left: 돌아가는 왼쪽 끝
            // right: 돌아가는 오른쪽 끝
    //⭐️ 반복문을 통해서 최적의 left 지점과 right 지점을 찾는 것!
    for left in 0..<name.count {
        var right = left + 1
        
        // left를 통해 0 (= A)는 건너뛰면서 right를 찾는다.
        while right < name.count && updownArray[right] == 0 {
            right += 1
        }
        
        // left 지점부터 들렀다가 돌아가는 경우와 right 지점부터 들렀다가 돌아가는 경우의 이동 횟수를 구한다.
        let leftFirst = left * 2 + (name.count - right)
        let rightFirst = (name.count - right) * 2 + left
        
        // 기존의 좌우 조작의 기본 값과 비교해서 최솟값을 찾는다.
        leftright = min(leftright, leftFirst)
        leftright = min(leftright, rightFirst)
    }

    return totalUpdown + leftright
}