[백준 24511] queuestack [Java]

문제

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

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

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

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

입력

출력

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

---

풀이

문제에서 주어진 'queuestack' 이란,  i번째 구조가 주어지는 수열 A의 값에 따라 Queue 또는 Stack가 되는 자료구조다.

단순히 구현만 하면 될 것 같지만, N * M은 시간초과가 발생한다.

문제를 단순화해보자.

 

i번째 자료구조 A(i) = 0 일 때, Queue에 대한 pop, push의 결과( x(i+1) )가 반환된다.

즉, x(i)에 대해 Queue의 요소 간 swap한 결과를 얻을 수 있다.

A(i) = 1일 때, Stack에 대한 pop, push의 결과는 동일하다. 따라서 생략 가능하다.

 

예상되는 결과를 미리 저장해둘 Deque구조의 queuestack에 A(i) = 0일 때 요소들을 순서대로 push해주자. ...(1)

이어서 수열 B의 요소들을 add해서 만들어진 queuestack에 대해 pop한 결과를 출력하면 된다. ...(2)

 

아래에서 문제의 주어진 예제를 통해 위 과정을 확인해보자.

수열 A의 값에 따라 'queuestack'의 0, 3번은 Queue이고, 1, 2번은 Stack이다.

1, 2번은 무시해주자.

초기상태 [1, 2, 3, 4]에 대해 수열 C의 원소 [4, 1, 2]를 하나씩 x(0)으로 계산해보자.

• 첫 번째 원소(4) 삽입 : 0번 Quque와 swap, 3번 Quque와 swap
• 두 번째 원소(1) 삽입 : 0번 Quque와 swap, 3번 Quque와 swap
• 세 번째 원소(2) 삽입 : 0번 Quque와 swap, 3번 Quque와 swap

결국 0번 Queue의 요소가 3번 Queue로 넘어가고, 3번에 있던 요소가 출력되는 과정의 반복이다.

 

(1) 'queuestack'의 Queue의 요소들을(1, 4) 순서대로 push

index	0	1	2	3	4
element	4	1

 

(2) 수열 B의 요소들을(2, 4, 7) 순서대로 add

index	0	1	2	3	4
element	4	1	2	4	7

 

이렇게 만들어진 Deque구조에 대해 pop한 결과를 출력하면 된다.

---

소스코드

보기

---

출처

24511번: queuestack