백준 1158 - 요세푸스 문제(Swift): LinkedList구현!!

1158번: 요세푸스 문제

입력

• 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
• 입력이 1이상, 5000이하의 자연수이기 때문에 0의 입력에 대한 문제를 처리할 필요가 없다!!

Node구현

class Node {
    let value: Int
    var next: Node?
    var prev: Node?

    init(value: Int, prev: Node? = nil, next: Node? = nil) {
        self.value = value
        self.prev = prev
        self.next = next
    }
}

null

• 위 사진처럼 값을 가지는 value프로퍼티와 이전 Node, 다음 Node를 가리켜주는 prev와 next를 하나의 Node로 구성하였다.

LinkedList구현(Circular LinkedList

null

struct LinkedList {
    var head: Node?
    var tail: Node?

    init(size: Int) {
        var currentNode = Node(value: 1)
        self.head = currentNode
        for _ in 1..<size {
            let nextNode = Node(value: currentNode.value + 1)
            currentNode.next = nextNode
            nextNode.prev = currentNode
            currentNode = nextNode
        }

        self.tail = currentNode
        self.tail?.next = self.head
    }

    mutating func removeFirst() -> Int? {
        let returnHead = self.head

        self.tail?.next = self.head?.next
        self.head = self.head?.next
        self.head?.prev = self.tail

        guard let value = returnHead?.value else { return nil }

        return value
    }

    mutating func moveTo(number: Int) {
        for _ in 0..<number {
            self.tail = self.head
            self.head = self.head?.next
        }
    }
}

• 해당 문제를 봤을 때 이니셜라이즈는 무조건 하나 이상의 linkedList를 만들기 때문에 0이 들어오는 상황을 신경쓰지 않고 만들어줬다. 1부터 N까지 각각 하나의 값을 N개의 Node를 만들어서 연결해준다.
• 또한 문제를 봤을 때 이미 구성된 LinkedList에서 k번째로 이동하여 제거만 하면 되기 때문에 k번째로 이동하는 moveTo메소드, head의 Node를 제거해주는 removeFirst()로 구성하였다.

removeFirst()에 관한 고찰

첫 코드

mutating func removeFirst() -> Int? {
    defer {
        self.tail?.next = self.head?.next
        self.head = self.head?.next
        self.head?.prev = self.tail
    }

    guard let value = self.head?.value else { return nil }

    return value
}

• 기존에는 defer를 사용하여 현재 head값을 리턴해주고 defer내에서 head와 tail을 바꿔주는 형태로 구성하였다.

수정 후 코드

mutating func removeFirst() -> Int? {
    let returnHead = self.head

    self.tail?.next = self.head?.next
    self.head = self.head?.next
    self.head?.prev = self.tail

    guard let value = returnHead?.value else { return nil }

    return value
}

• 이후 head값을 상수에 저장하고 tail과 head에 관해 교체해준 이후 이전에 저장한 상수를 return해주는 형태로 바꿨다.

null

• 수정 후 메모리는 동일하지만 속도가 조금 더 빨라진것을 볼 수 있다.
• 가독성면에서나 속도면에서나 defer사용은 자제해야할것 같다.

실행 코드

let inputs = readLine()!.split(separator: " ").map { Int($0)! }
let n = inputs[0]
let k = inputs[1]

var answer: [Int] = []
var result = ""

var josephus = LinkedList(size: n)

for _ in 0..<n {
    josephus.moveTo(number: k-1)
    if let value = josephus.removeFirst() {
        answer.append(value)
    }
}

result = answer.description.replacingOccurrences(of: "[", with: "<")
print(result.replacingOccurrences(of: "]", with: ">"))

• answer의 description "[3, 6, 2, 7, 5, 1, 4]"을 스트링으로 받아 "["는 "<"로 교체, "]"는 ">"로 교체하였다.
• 배열을 통해 ["[", "]"]를 ["<", ">"]를 인자로 넣어서 교체해주는 메소드를 봤었던 것 같은데 찾지를 못하여 replacingOccurences를 두번 쓴게 좀 아쉬운것 같다.