[BOJ 24511] 백준 24511번 - queuestack

		2022 ICPC Sinchon Winter Algorithm Camp Contest 풀이
A		[BOJ 24510] 시간복잡도를 배운 도도
B		[BOJ 24509] 상품의 주인은?
C		[BOJ 24511] queuestack
D		[BOJ 24512] Bottleneck Travelling Salesman Problem (Small)
E		[BOJ 24513] 좀비 바이러스
F		[BOJ 24514] n번째 숫자 찾기
G		[BOJ 24515] 히히 못가
H		[BOJ 24516] 잘 알려진 수열 구하기
J		[BOJ 24517] 카드 게임과 쿼리
K		[BOJ 24519] Bottleneck Travelling Salesman Problem (Large)

1. 문제

$24511$. queuestack (2022 ICPC Sinchon Winter Algorithm Camp Contest C번)

백준 24511번 - queuestack (https://www.acmicpc.net/problem/24511)

2. 풀이

[그림1]처럼 스택은 임의의 $x$를 자료구조에 삽입한 뒤 원소를 pop하면, 삽입했던 $x$가 그대로 pop된다. 따라서 스택은 없다고 봐도 무방하므로 무시한다.

[그림2]처럼 큐는 임의의 $x$를 자료구조 삽입하고, 큐에 들어있던 제일 마지막 원소가 pop된다. 총 $N$개의 자료구조가 있고 여기서 스택을 무시하면 임의 개수의 큐만이 남게 된다.

첫번째 큐의 마지막에서 pop한 원소가 두번째 큐의 첫번째 원소로 push되고, 두번째 큐의 마지막에서 pop한 원소가 세번째 큐의 첫 번째 원소로 push되고… 이러한 작업이 반복되고 최종적으로 마지막 큐의 마지막 원소가 pop됨을 알 수 있다. 이는 [그림3]에서도 확인 가능하다.

그리고 이를 하나로 연결시켜 단 하나의 큐로 생각할 수 있다. 즉 임의 개수의 큐에 문제의 작업을 하는 과정은 결국, 제일 처음 큐에 하나의 원소를 push하고 제일 마지막 큐의 마지막 원소를 pop하는 과정과 동일하다.

$A[i]=0$인 큐들이 전부 하나의 큐로 연결된다. (이 하나의 큐를 원래 큐에 구분하기 위해 Queue로 작성한다.) 제일 마지막 Queue의 원소가 Queue의 front가 되고, 제일 처음 Queue의 원소가 Queue의 back이 된다. 그리고 삽입할 원소들까지 Queue에 차례로 push해준다. 이렇게 거대한 하나의 Queue가 완성된다.

삽입을 총 $M$번 하므로 pop되어 나오는 원소의 개수도 총 $M$개이다. 따라서 Queue에서 $M$개의 원소를 pop하여 출력하면 정답이다. Queue에 삽입되는 원소들을 push해주었기 때문에 Queue의 최소 길이는 $A(i)$가 전부 $1$이라 가정해도 $M$이다. 따라서 $M$개의 원소를 출력하는 데에는 아무 문제가 없다.

3. 채점 결과

4. 회고

.

5. 코드