백준 24511 - Swift

 

백준 큐, 스택 알고리즘 풀이 (24511)

 

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

 

 

문제를 손으로 직접 써가면서 풀다보면

Stack은 변화가 없고 Queue에서만 변화가 있다는 걸 알 수 있음

그래서 Queue만 처리해주면 됨!

 

"Queue는 선입선출 + 들어오는 값의 크기인 n만큼 Output도 생성됨"

1-4까지 뒤부터 차례대로 Queue에 먼저 들어가 있는 원소들이 

빠지기 때문에 그 값들을 처리하고 생각하면 됩니다.

 

그래서 ..

첫번째 원소가 4인 큐에 있는 원소부터 빠지기 때문에

answer = [Int]() 배열이 있을 때

Queue안에 있는 원소들을 모두 추가하고

answer의 크기가 input 크기에 비해 부족하다면 

그 값 만큼 input 에서 removefirst()를 해주면 된다는 말

 

헷갈린다면 2,4,7 이후에 다른 숫자를 계속 넣으면서 확인해보시면 쉬움

(2,4,7,6,8,9 를 넣으면 (4, 1)(2,4,7)(6) 이렇게 출력되는것을 확인할 수 있어요)

 

import Foundation

let n = Int(readLine()!)!
let type = readLine()!.split(separator: " ").map { Int($0)! }
let firstElement = readLine()!.split(separator: " ").map { Int($0)! }
let count = Int(readLine()!)!
var input = Array(readLine()!.split(separator: " ").map { Int($0)! }.reversed())

var tempQ = [Int]()
for i in 0..<n {
    if type[i] == 0 {
        tempQ.append(firstElement[i])
    }
}

var answer = [Int]()
for _ in 0..<count {
    answer.append(tempQ.popLast() ?? input.removeLast())
}

print(answer.map({ String($0) }).joined(separator: " "))

 

 

먼저 if문을 통해서 큐의 원소들을 뽑아서 저장하고

pop을 통해서 순서대로 answer에 쌓아주면 됨

 

근데 여기서 왜 input을 reversed해서 removeLast를 하냐면...

맨첨에 removeFirst를 했는데 계속 시간초과가 나서 왜지? 하고 GPT한테 물어봤더니

 첫 번째 요소를 제거하고 나머지 요소를 앞으로 이동시키기 때문에 O(count * count) 시간 복잡도가 될 수 있습니다. 
 이는 최악의 경우 상당히 비효율적일 수 있습니다.

그에 비해 removeLast()는 O(1)의 시간복잡도를 가지고 있기 때문에 

해당 부분을 적용하기 위해서 reversed()해서 했더니 통과했음

 

사실 맨처음에는 모두 처리해야하나? 싶어서 그렇게 했는데 시간초과가 계속나서

파이썬으로 풀었다가 swift로 풀었다가 하면서 찾았습니다. .. . .

시간초과로 헤매는분이 있을까봐 실버지만.. 블로깅..