[백준 10811] 바구니 뒤집기 (Swift)

10811번: 바구니 뒤집기

n개의 바구니들이 있을 때, m번 바구니 순서를 역순으로 만든다.

m개의 시행마다 i부터 j까지라는 범위가 주어진다. (1 ≤ i ≤ j ≤ n)

• i == j 일 때는 바꿀 필요가 없다.
• j - i == 1 일 때는 두 요소의 자리를 바꿔준다
  • ``swapAt(*:*:)` 사용
• 나머지 경우에는 i부터 j까지의 바구니들을 뒤집어야 한다.
  • i 부터 j까지 뒤집는 바구니들 외에 나머지 바구니들은 그대로 유지된다.
  • 뒤집는 바구니들의 앞 부분 = head : 그대로 유지
  • 뒤집는 바구니들 = reversed
    • reversed() 사용
  • 뒤집는 바구니들의 뒷 부분 = tail : 그대로 유지
  • head + reversed + tail 의 부분 배열들을 모두 합쳐 하나의 배열로 만든 다음, 그 배열을 새로운 바구니들로 할당한다.

이번 문제에서는 바구니를 뒤집는 작업 자체가 오래 걸리지 않도록, 기본제공 메서드들 중 시간복잡도가 낮은 메서드들 위주로 사용하려 했다.

문제 풀이에 사용한 ``swapAt(*:*:)와reversed()` 모두 O(1) 의 시간복잡도를 가져 사용하기 좋았다. (정리한 문서)

---

풀이 (나의 풀이)

let inputArr = readLine()!.split(separator: " ").map { Int($0)! }
let n = inputArr[0]
let m = inputArr[1]
var baskets = Array(1...n)
for _ in (1...m) {
    let exchange = readLine()!.split(separator: " ").map { Int($0)! }
    let start = exchange[0] - 1
    let end = exchange[1] - 1
    if start == end {
        continue
    }
    if end - start == 1 {
        baskets.swapAt(start, end)
        continue
    }
    let head = Array(baskets[baskets.startIndex..<start])
    let tail = Array(baskets[end+1..<baskets.endIndex])
    let reversed = Array( baskets[start...end].reversed())
    baskets = head + reversed + tail
}
baskets.forEach { print($0, terminator: " ")}

다른 풀이

같은 시간복잡도를 갖는 풀이 중에 다른 방식으로 푼 코드도 있었다.

이 경우 i부터 j라는 범위에서 “i와 j 자리 바꾸기 → i+1과 j-1 자리 바꾸기 → i+2와 j-2 자리 바꾸기 …” 와 같은 식으로 주어진 바구니를 뒤집고, i+n이 j+n보다 작거나 같아질 때까지 반복한다.

직접 뒤집지 않고 한 쌍씩 자리를 바꿔도 결과적으로 뒤집을 수 있다는 점에서 좋은 것 같다.

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

var basket = [Int](0...n)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    var start = input[0], end = input[1]
    while start < end {
        basket.swapAt(start, end)
        start += 1
        end -= 1
    }
}

basket[1...].forEach { print($0, terminator: " ") }

또 다른 풀이에서, 마지막 줄 출력 부분에 좋은 코드가 있었다.

내 방식은 끝에 공백이 생기는데, 아래 방식은 공백이 생기지 않는다는 점에서 좋다. 나도 joined를 잘 활용해 봐야겠다.

// 내 방식
baskets.forEach { print($0, terminator: " ")}

// 새로운 방식
print(baskets.map{ String($0) }.joined(separator: " "))