[백준(BOJ)] 24511 queuestack - 스위프트 (Swift)

[Silver III] queuestack - 24511

문제 링크

성능 요약

메모리: 80628 KB, 시간: 164 ms

분류

자료 구조, 덱, 큐, 스택

제출 일자

2024년 1월 2일 22:02:41

문제 설명

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1$1$번, 2$2$번, ... , N$N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

•  x0$x_0$을 입력받는다.
•  x0$x_0$을 1$1$번 자료구조에 삽입한 뒤 1$1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1$x_1$이라 한다.
•  x1$x_1$을 2$2$번 자료구조에 삽입한 뒤 2$2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2$x_2$이라 한다.
• ...
•  xN−1$x_{N-1}$을 N$N$번 자료구조에 삽입한 뒤 N$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN$x_N$이라 한다.
•  xN$x_N$을 리턴한다.

도현이는 길이 M$M$의 수열 C$C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1$1$ 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N$N$이 주어진다. (1≤N≤100000$1 \leq N \leq 100\,000$)

둘째 줄에 길이 N$N$의 수열 A$A$가 주어진다. i$i$번 자료구조가 큐라면 Ai=0$A_i = 0$, 스택이라면 Ai=1$A_i = 1$이다.

셋째 줄에 길이 N$N$의 수열 B$B$가 주어진다. Bi$B_i$는 i$i$번 자료구조에 들어 있는 원소이다. (1≤Bi≤1000000000$1 \leq B_i \leq 1\,000\,000\,000$)

넷째 줄에 삽입할 수열의 길이 M$M$이 주어진다. (1≤M≤100000$1 \leq M \leq 100\,000$)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M$M$의 수열 C$C$가 주어진다. (1≤Ci≤1000000000$1 \leq C_i \leq 1\,000\,000\,000$)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 C$C$의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

 

풀이

우선 해당 문제의 예시를 풀어보았습니다.

예시 풀이

 

풀이를 보았을 때, 사실 스택은 아무 의미가 없고, 큐에 따라 정해짐을 알 수 있었습니다.

 

따라서 큐인 것들만 배열에 추가하고, 다시 만들어보았습니다.

이러한 규칙이 발견되었습니다.

따라서 queuestack에 삽입할 원소는 위의 순서대로 진행하면 됨을 알 수 있습니다.

 

만약 m(삽입할 원소의 개수)이 큐보다 크다면, 큐에 있는 값을 reverse해준 뒤 출력해주고,

남은 만큼 들어온 순서에 대한 값을 출력해주면 됩니다.

 

다음은 코드입니다.

let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map{ Int(String($0))! }
let b = readLine()!.split(separator: " ").map{ Int(String($0))! }
var m = Int(readLine()!)!
let c = readLine()!.split(separator: " ").map{ Int(String($0))! }
var queue = [Int]()
var ans = ""

for i in 0..<a.count {
    if a[i] == 0 {  // 큐 일때만 추가 (스택은 의미가 없음)
        queue.append(b[i])
    }
}

// m이 queue에 있는 개수보다 많거나 같을 때 -> queue에 있는 것들 + 삽입된 원소들 추가
if m >= queue.count {
    for i in queue.reversed() {
        ans += "\(i) "
    }
    for i in 0..<m - queue.count {
        ans += "\(c[i]) "
    }
} else {    // m이 더 queue에 있는 개수보다 더 적을 때 -> queue에 있는 것들만 해도 충분
    for i in stride(from: queue.count - 1, to: queue.count - m - 1, by: -1) {
        ans += "\(queue[i]) "
    }
}
print(ans)