[백준/Swift] 2164번: 카드2

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

2164번: 카드2

 

큐를 이용한 문제인데 사실 cpp로 풀어봤다.

그때는 queue의 push, pop로 간단하게 풀었는데,,, Swift로 하니까 시간 초과가 발생한다 흑흑

(역시.. cpp가 빠르긴 하구나... 부럽다^^)

 

[시간 초과 코드]

import Foundation

let N = Int(readLine()!)!
var card = [Int]()
for i in 1...N { card.append(i) }
while card.count != 1 {
    card.removeFirst() //1. 제일 위 카드 버리기
    card.append(card.removeFirst()) //2. 제일 위 카드 제일 아래로 옮기기
}
print(card[0])

 

그래서 흠.. 어떤 게 문제인지 찾아봤다. 아마 배열 원소를 삭제하고 뒤에 붙이는 게 문제였을 거 같다.

 

[최종 코드]

import Foundation

/*
 N장의 카드, 1번 카드가 제일 위에, N번 카드가 제일 아래
 1. 제일 위에 있는 카드 버리기
 2. 제일 위 카드를 제일 아래로 옮기기
 3. 한 장 남을 때까지 반복
 */

let N = Int(readLine()!)!
var card = Array(1...N)
var top = 0
if N == 1 {
    print(1)
}else {
    while true {
        card[top] = 0                   //1. 제일 위 카드 버리기
        card.append(card[top + 1])      //2-1. 제일 위 카드 제일 아래로 옮기기
        card[top + 1] = 0               //2-2. 제일 위 카드 없애기
        if card[card.count - 2] == 0 {  //앞에서부터 0이 채워짐
            break
        }
        top += 2
    }
    print(card[card.count - 1])
}

 

N == 1 일때를 처리하지 않으니 런타임 에러가 계속 발생했다.

 

---

 

알고리즘 공부를 하면서 문제를 다시 풀어봤다. 전에 queue 배열을 사용하니 시간초과가 났던 것이 생각나서 뒤로 원소를 계속 넣는 쪽으로 진행했다. 그런데 이전 코드와 조금 다른 부분이 발생했다.

import Foundation

let n = Int(readLine()!)!
var queue = Array(1...n)
var front = 0

if n == 1 {
    print(1)
}else {
    while true {
        queue[front] = 0
        queue.append(queue[front+1])
        queue[front+1] = 0
        if queue[queue.count - 3] == 0 {
            break
        }
        front += 2
    }
    print(queue[queue.count - 1])
}

 

바로 while 문을 빠져나오는 조건인데, 전에는 -2를 해줬지만 지금은 -3으로 해줬다.

카드 2개가 남으면 맨 뒤 카드가 정답인데 카드가 2개 남았다는걸 어떻게 아냐 하면 뒤에서부터 3번째가 0이면 남은 카드가 2개다.

이전에 -2 는 카드가 1개 남을 때까지 돌려준 것이기 때문에.. 사실 어차피 1번 더 돌아가는 거라 시간 복잡도에 영향이 없지만 그래도 다른 방향으로 생각했다는 걸 남기고 싶었다!