[알고리즘] Swift -백준 #1835 (카드)

문제링크

https://www.acmicpc.net/problem/1835

1835번: 카드

 

문제

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다. 마술을 하는 순서는 다음과 같다.

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다. 카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

 

 

역시뮬레이션하는 문제로 초기상태를 구해야되서 역순으로 진행해야한다...

머리가 어지워서 진짜 힘들었다...후하후하

---

풀이

var num = Int(readLine()!)!
var arr = [Int]()

for i in stride(from: num, through: 1, by: -1) {
    arr.insert(i, at: 0)
    for _ in 1...i {
        let last = arr.popLast()
        arr.insert(last!, at: 0)
    }
}


for i in arr {
    print(i, terminator: " ")
}

 

결과

 

 

 

덱을 구현하여 덱을 이용 (덱 구현 출처 ; https://developer-p.tistory.com/146)

class Dequeue<T: Comparable> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func firstIndex(_ num: T) -> Int {
        let newQue = deQueue.reversed() + enQueue
        if let i = newQue.firstIndex(where: {$0 == num}) {
            return i
        }
        return 0
    }
}


var num = Int(readLine()!)!
var deq = Dequeue<Int>([])

for i in stride(from: num, through: 1, by: -1) {
    deq.pushFirst(i)
    for _ in 1...i {
        deq.pushFirst(deq.popLast())
    }
}

for _ in 0..<deq.count {
    print(deq.popFirst(), terminator: " ")
}