안녕하세요 이번 시간에는 덱(Deque)을 이용한 코딩테스트 문제의 유형을 분석해보도록 하겠습니다. 덱의 경우 주로 출제되는 유형은 하나로 요약할 수 있습니다. 바로 순환하는 사이클을 가지는 문제입니다. 덱의 특성상 맨 앞과 맨 뒤에서 데이터를 참조할 수 있기 때문에 맨 앞의 값을 뽑아서 맨 뒤로 추가하거나 맨 뒤의 값을 뽑아서 맨 앞으로 추가하게 되면 덱 내의 원소들이 순환하게 됩니다. 따라서 이런 특성을 이용하면 순환하는 로직을 가진 문제를 쉽게 풀 수 있습니다.
백준 2164(카드2) 문제의 경우 제일 위에 있는 카드를 바닥에 버리고 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮겼을 때 최종 카드를 구하는 문제입니다. 제일 위에 있는 카드를 가장 앞쪽으로 잡고 덱을 생성한 후 앞에서 두 번 뽑은 다음 마지막에 뽑은 값을 덱의 가장 뒤에 추가하여 덱이 1개 남을 때까지 반복하면 문제를 풀 수 있습니다.
백준 1158(요세푸스 문제) 문제의 경우 원을 이루면서 앉아있을 때 k번째 사람이 계속 제거되는 순서를 구하는 문제입니다. 덱을 만든 후 k번 동안 제일 앞의 값을 뽑아서 제일 뒤로 추가한 후 k번 이후 제일 앞의 값을 뽑는 방식으로 문제를 풀 수 있습니다.
백준 1021(회전하는 큐) 문제의 경우 N개의 원소를 포함하는 큐에서 특정 원소를 뽑아내기 위한 연산의 최솟값을 구하는 문제입니다. 덱을 만든 후 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우의 최솟값을 결과에 누적하여 저장하는 방식으로 문제를 풀 수 있습니다.
백준 2346(풍선 터뜨리기) 문제의 경우 풍선을 터뜨려 적혀있는 수만큼 이동했을 때 터진 풍선의 번호를 출력하는 문제입니다. 덱을 만들어 덱 안에 풍선 클래스를 넣은 후 풍선 클래스의 번호에 따라 왼쪽 또는 오른쪽으로 이동하여 값을 뽑아내면 풀 수 있습니다.
