[swift] 백준 - 2164번: 카드2

2164번: 카드2

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

- 첫 번째 숫자는 지우고, 두 번째 숫자는 제일 뒤로 보냅니다.(앞에서 사라짐)

해당 명령을 반복하여 마지막 남는 하나의 숫자를 출력합니다.

 

- 기본적인 큐의 형태로 풀면되지만

숫자를 지우는 과정에서 remove함수를 쓰게 되면

시간 초과가 납니다.

 

- 이유는 인덱스 전체를 앞으로 당겨오는 과정에서

O(n)만큼 시간이 걸리기 때문입니다.

 

- 따라 시간제한에 통과할 수 있게 코드를 짜면 되겠습니다.

 

---

 

나의 풀이

import Foundation

let N = Int(readLine()!)!

var card: [Int?] = (1...N).map { $0 }
var head = 0

while true {
    guard card.count != 1 else { print(1); break }
    card[head] = nil
    if card[card.count-2] == nil { print(card[card.count-1]!); break }
    card.append(card[head+1])
    card[head+1] = nil
    head += 2
}

 

- head라는 인덱스 기억변수를 만들었습니다.

해당 변수는 배열이 remove 되는 게 아닌

nil로 변하기 때문에

남아 있는 배열을 건너뛰어주기 위해 생성했습니다.

 

- head는 한 번의 반복에서 2개의 값을 nil로 만들기 때문에

반복마다 + 2씩 더해주게 됩니다.

 

- 반복문을 돌다 마지막에서 2번째인 값이 nil이 된다면

값은 하나가 남았다는 것이고

해당 마지막값을 출력해 주면 됩니다.

 

- 만약 N이 1이라면 런타임오류가 뜨기 때문에

guard문으로 count가 1이라면 1을 출력하게 예외를 뒀습니다.

 

---

 

참고할만한 풀이

var N = Int(readLine()!)!
var Q = (1...N).map{$0}

var cursor = 0
while cursor < N-1 {
    cursor += 2
    Q.append(Q[cursor-1])
    N+=1
}

print(Q[cursor])

 

- while문에 조건을 줘서 푸니

더 깔끔하게 코드가 나올 수 있네요.

 

---

let N = Int(readLine()!)!

var i = 1
while true {
    if N >= i , N < i*2 {
        break
    }else{
        i *= 2
    }
}
let remain = N-i
if remain == 0 {
    print(i)
}else {
    print(2*remain)
}

 

- 뭔가 큐를 사용하지 않고 풀 수 있을 거 같았는데

알고리즘이 생각나지 않아서 시도도 못했었습니다.

 

- 하지만 역시 누군가는 풀었네요..ㅎㅎ

 

---