[알고리즘] Swift - 카드2(백준2164)

 

문제

· 아이디어💡

 이 문제에 접근 방법은 두 가지가 있다. 하나는 큐를 구현해서 푸는 방법과 큐를 구현하지 않고 푸는 방법이 있다. 결론적으론 두 방법 다 같은 원리로 접근해서 푸는 방법이긴 하다. 포인터 큐를 사용할 예정인데, dequeue를 하면 front라는 제일 처음 인덱스를 +1을 계속해줌으로 써 dequeue를 한 배열은 배제하고 그 이후 인덱스부터 확인하는 방법이다. 큐를 구현하지 않고 푸는 방법도 같은 원리를 사용하는 방법이다.

· 코드 😵😵‍💫

1. 큐를 구현해서 푸는 방법

struct QueuePointer<T> {
  private var elements: [T] = []
  private var front = 0

  var isEmpty: Bool {
    elements.count < front + 1
  }

  var count: Int {
    elements.count - front
  }

  func peek() -> T? {
    front < elements.count ? elements[front] : nil
  }

  mutating func enqueue(with element: T) {
    elements.append(element)
  }

  @discardableResult
  mutating func dequeue() -> T? {
    if !isEmpty {
      defer { front += 1 }
      return elements[front]
    } else {
      return nil
    }
  }
}

func sol2164() {
    let cards = Int(readLine()!)!
    var list = QueuePointer<Int>()
    
    for i in 1...cards {
        list.enqueue(with: i)
    }
    
    while list.count != 1 {
    	list.dequeue()
        list.enqueue(with: list.dequeue()!)
    }
    
    print(list.dequeue()!)
    
}

sol2164()

 

2. 큐 없이 푸는 방법

func sol2164() {
    let n = Int(readLine()!)!
    var front = 0
    var cards: [Int] = []
    
    for i in 1...n {
        cards.append(i)
    }
    
    while cards.count - front > 1 {
        front += 1
        cards.append(cards[front])
        front += 1
    }
    
    print(cards[front])
}

sol2164()

 

· 시간 복잡도 ⁉️🤔

 시간복잡도는 O(N)이다. 이 문제는 O(N^2)으로 풀 수 없다. 시간초과가 발생하기 때문이다.

· 고려사항 🌟

 언어에 따라 Queue 라이브러리가 있으면 빠르게 풀 수 있고, 없다면 직접 구현하든지 혹은 그 원리를 사용해서 풀면 된다.