1107번: 리모컨

틀린 접근 1: bfs

채널을 바꾸는데 드는 최소 버튼 조작 수를 구하는 것이므로 당연히 최단거리 문제라고 생각을 했습니다. 그래서 아래처럼 버튼 하나하나 누를 때 마다 하나의 경우의 수를 만들어서 queue에 넣고 bfs로 최단거리를 구하고자 했습니다.

하지만 절대로 최단거리가 될 수 없는 불필요한 너무나 많은 경우의 수를 탐색하기 때문에 (숫자 누르고, + 누르고, 다시 숫자를 누르는 등) 문제를 해결할 수 없었습니다.

func bfs() {
    var queue = Queue()
    var check = Set<Int>()
    let now = (100, 0, PreviousButtonType.none)

    queue.push(now)
    check.insert(now.0)

    while !queue.isEmpty {
        let now = queue.pop()

        if now.0 == N { print(now.1); return }

        for button in buttons {
            let next = now.0.pushButton(button, now.2)
            if next.isValid && !check.contains(next) {
                queue.push((next, now.1 + 1, PreviousButtonType.number))
                check.insert(next)
            }
        }

        let plusOne = now.0 + 1
        if plusOne.isValid && !check.contains(plusOne) {
            queue.push((plusOne, now.1 + 1, PreviousButtonType.oper))
            check.insert(plusOne)
        }

        let minusOne = now.0 - 1
        if minusOne.isValid && !check.contains(minusOne) {
            queue.push((minusOne, now.1 + 1, PreviousButtonType.oper))
            check.insert(minusOne)
        }
    }
}

틀린 접근 2: case 나누어서 직접 계산하기

최솟값이 나올 수 있는 경우를 4가지로 나누었습니다.

1. 숫자 버튼 만으로 N에 접근할 수 있는 경우
2. 100에서 부터 up/down으로 N에 접근할 수 있는 경우
3. N보다 낮은 숫자로 가서 up 버튼으로 N에 접근하는 경우
4. N보다 높은 숫자로 가서 down 버튼으로 N에 접근하는 경우

하지만 이 경우에는 3, 4번 경우의 수를 구할 때 N보다 높은 수 (혹은 낮은 수)에서 숫자버튼 만으로 접근할 수 있는 수가 없을 때의 예외 처리가 쉽지 않았습니다. (ex. 모든 숫자 버튼이 고장난 경우 while에서 무한루프 발생!)

func solve() {
    if N == 100 {
        print(0)
        return
    }

    var buttonPush = Int.max

    if N.isPossible {
        buttonPush = N.length
    }

    let onlyUpDown = abs(N - 100)

    let withUp: Int = {
        var n = N
        var pushUp = 0
        while !n.isPossible && n >= 0 {
            n -= 1
            pushUp += 1
        }
        return n.length + pushUp
    }()

    let withDown: Int = {
        var n = N
        var pushDown = 0
        while !n.isPossible && n < 1000000 {
            n += 1
            pushDown += 1
        }
        return n.length + pushDown
    }()

    print(min(buttonPush, onlyUpDown, withUp, withDown))
}

solve()

옳은 접근: 브루탈 포스

우리가 주목할 포인트는 N의 범위입니다. N의 범위는 500,000로 완전탐색을 해도 충분히 시간 내에 문제를 해결할 수 있습니다. 물론 - 버튼을 활용해서 500,000 보다 큰 수에서 내려오는 경우도 감안해야하므로 범위를 2배인 1,000,000으로 해서 탐색해야 합니다. (1,000,001 이상의 경우 출발점인 100에서 올라가는 것이 더 빠른 방법입니다. 탐색할 필요가 없습니다.)

//✅ 탐색을 위해 필요한 메소드들
extension Int {
		// 숫자 버튼을 눌러서 갈 수 있는 채널인지
    var isPossible: Bool {
        guard self >= 0 else { return false }
        let stringArray = String(self).map { String($0) }
        for string in stringArray {
            if xButtons.contains(string) {
                return false
            }
        }
        return true
    }

		// 채널의 길이 (숫자버튼을 누르는 횟수)
    private var length: Int {
        String(self).map { String($0) }.count
    }
    
		// 채널에서 N까지 가기위한 모든 비용: 숫자 누르는 횟수 + up/down 버튼 누르는 횟수
    var cost: Int {
        self.length + abs(self - N)
    }
}

// 입력 받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!

// 🚫 M == 0이면 입력을 받지 않는다!
var xButtons = [String]()
if M > 0 {
    xButtons = readLine()!.split(separator: " ").map { String($0) }
}

// 처음 채널인 100에서 N까지 가기 위해 up/down 버튼을 누르는 횟수
var ans = abs(N - 100)

// 가능한 모든 채널을 탐색하면서 숫자 버튼으로 접근이 가능하면 cost를 기존의 최솟값과 비교한다.
for channel in 0...1000000 {
    if channel.isPossible {
        ans = min(ans, channel.cost)
    }
}

print(ans)

성능 이슈

1. Int → String을 지양하자!

위 풀이는 성능 이슈가 있습니다. 원래 Swift는 Python보다 훨씬 좋은 성능을 가지고 있습니다만, 위 코드로 채점을 하면 5배 가량의 실행시간 차이가 있었습니다. (파이썬 224ms, 스위프트 924ms)

이유는 Swift는 정수 → 문자열 변환이 훨씬 더 오랜 시간이 걸리기 때문입니다. 한두번 실행하는 부분이라면 isPossible과 length 부분을 위처럼 String을 이용해도 관계 없지만 반복문 안에서 N번 실행하는 경우라면 성능 이슈가 발생할 수 밖에 없습니다. 위 코드의 isPossible과 length 부분을 String을 사용하지 않도록 개선해봅시다.

extension Int {
    var length: Int? {
        var now = self
        
				// 0인 경우 예외처리
        if now == 0 {
            if xButtons.contains(0) {
                return nil //👉 0이 고장나면 불가
            } else {
                return 1 //👉 0이 고장 안 나면 길이 1
            }
        }
        
        var length = 0
        //✅ 1의 자리수부터 버튼으로 누를 수 있는지 확인
        while now > 0 {
            guard !xButtons.contains(now % 10) else { return nil } //🚫 못 나누면 nil
            now /= 10 //👉 나눌 수 있다면 다음 자릿수 확인
            length += 1 //👉 길이에 + 1
        }
        
        return length
    }
}

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var xButtons = Set<Int>()
if M > 0 {
    xButtons = Set(readLine()!.split(separator: " ").map { Int(String($0))! })
}

var ans = abs(N - 100)

for channel in 0...1000000 {
		//✅ channel을 버튼으로 누를 수 있을 때만 확인
    if let length = channel.length {
        ans = min(ans, length + abs(channel - N))
    }
}

print(ans)

2. Set과 Array의 contain

Set(집합)과 Array(배열)에 모두 정의된 contain 메소드의 경우 Set의 경우 O(1), Array의 경우 O(n)의 시간복잡도를 가지고 있습니다. 하지만 위 문제의 경우 n의 길이가 최대 10 밖에 되지 않습니다. 따라서 xButton을 Set으로 구현하던 Array로 구현하던 성능 차이는 거의 없을 것으로 예상되었습니다.

실제 실행한 결과는 오히려 Array로 구현한 것이 더 실행이 빨리 되는 놀라운(?!) 결과가 있었습니다. Set의 경우 Contain을 구현할 때 Hash 값을 사용합니다. 따라서 element가 적은 경우 오히려 element를 hash 값으로 변경하는 작업이 element을 완전 탐색하는 것보다 긴 시간이 걸리는 것 같습니다. (제 추론입니다.)

이 이슈의 경우 좀 더 알아봐야 할 것 같습니다!

// Set으로 구현: 실행 시간 85ms
var xButtons = Set<Int>()
if M > 0 {
    xButtons = Set(readLine()!.split(separator: " ").map { Int(String($0))! })
}

// Array로 구현: 실행 시간 24ms
var xButtons = [Int]()
if M > 0 {
    xButtons = readLine()!.split(separator: " ").map { Int(String($0))! }
}