Swift - 백준 2164번 카드2 (큐)

while문을 사용하여 큐를 구현하였지만 시간초과가 되었으며 이를 해결해보겠습니다

 

문제의 코드는 아래와 같습니다. 아래 코드에서 잘못된 부분은 while문에 있습니다

 

var arr: [Int] = []
var line = Int(readLine()!)!
for i in 1...line {
    arr.append(i)
}

while arr.count != 1 {
    arr.removeFirst()
    let first = arr.first!
    arr.removeFirst()
    arr.append(first)
}
print(arr.first!)

 

문제점

여기서 바로 문제는 arr.removeFirst() 입니다. 그렇다면 왜 문제가 되는가?

 

arr는 배열이며 removeFirst() 메서드를 사용하게 된다면 가장 첫번째 원소를 지우기 때문에 뒤에 있는 모든 값들을 한칸씩 앞으로 땡겨야하기 때문입니다. 그렇게 되면 앞당기는 갯수만큼 시간이 소모되기 때문에 문제를 해결할 수 없게 됩니다.

 

해결방법

위에서 문제는 원소를 삭제함에 따라서 계속 원소값을이 이동하기에 시간초과가 발생한다고 설명하였습니다. 그렇다면 방법 중 하나로 원소를 삭제하지 않는 것을 생각해볼 수 있겠습니다. 그럼 해결 방법으로 Queue 를 생각해볼 수 있겠습니다.

 

// 배열 대신 원형 큐를 구현하기 위해 배열과 두 개의 인덱스를 사용
var queue: [Int] = []
var front = 0
var back = 0

// 입력 받기
let line = Int(readLine()!)!

// 큐 초기화
for i in 1...line {
    queue.append(i)
}
back = queue.count

// 큐에서 하나의 요소가 남을 때까지 반복
while (back - front) != 1 {
    front += 1  // 첫 번째 요소 제거(인덱스 증가)
    
    let first = queue[front]
    front += 1  // 첫 번째 요소를 두 번째로 바꿔치기
    queue.append(first) // 뒤에 요소 추가
    back += 1  // back 인덱스 증가
}

// 마지막 요소 출력
print(queue[front])