더블 하노이 알고리즘

아래 문제는 코딜리티에서 제공하는 더블 하노이의 문제입니다🧑🏻‍💻

문제 제시

You are given N disks and two rods, each with one initial disk.

On the left rod, disks can be placed in decreasing order of size (smaller disks on top of bigger ones). On the right rod, disks can be placed in increasing order of size (bigger disks on top of smaller ones). Note that it is not permissible to place two disks of equal size on top of each other. The initial disks cannot be moved.

Write a function:

public func solution(_ A : inout [Int], _ L : Int, _ R : Int) -> Int

that, given an array A of integers representing the sizes of the N disks and two integers L and R representing the size of the initial disks on the left and right rods respectively, returns the maximum number of disks from A that can be placed on the rods while satisfying the rules presented above.

Examples:

1. Given A = [2, 3, 3, 4], L = 3 and R = 1, your function should return 3, since only three disks can be placed on the rods. Note that the disk of size 2 can be placed on either the left rod or the right rod.

2. Given A = [1, 4, 5, 5], L = 6 and R = 4, your function should return 4.

3. Given A = [5, 2, 5, 2], L = 8 and R = 1, your function should return 4.

4. Given A = [1, 5, 5], L = 2 and R = 4, your function should return 2.

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int], _ L : Int, _ R : Int) -> Int {
    var LStack: [Int] = [L]
    var RStack: [Int] = [R]
    
    for i in 0..<A.count{
        if A[i] < L && !(LStack.contains(A[i])) {
            LStack.append(A[i])
        } else if A[i] > R && !(RStack.contains(A[i])) {
            RStack.append(A[i])
        }
    }
    
    let Lcount = LStack.count - 1
    let Rcount = RStack.count - 1
    let answer = Lcount + Rcount
    
    return answer
}

사용된 개념

 - 하노이

 - 반복 / 조건문

 - 스택

문제 뒷담화

이번 문제는 코딜리티 사이트에서 영어 문제를 보며 처음 도전을 해보았다.

아무래도 영어로 나오다보니 프로그래머스에서 익숙해진 나로써 영어 지문 해석에 시간을 좀 많이 쏟았다.

해당 문제를 요약해보자면 주어진 배열에서 양 하노이탑에 요소들을 넣어주고 최종적으로 요소들이 몇개 빼주었는지 반환하는거라 생각했다.

그렇게 테케를 다 통과하는 코드를 짜고 제출을 했는데...!

이렇게 100프로 통과가 아닌 큰 샘플의 경우 타임아웃이 났다😭

아마 로직상 더 시간복잡도를 간결하게 구현해볼 수 있을것 같다👍🏻