문제

자세한 문제 내용은 ‘카드2‘를 클릭하세요.

풀이

문제는 간단합니다. 큐에 1부터 n까지의 카드를 넣고, 큐에서 가장 위에 있는 카드를 버리고 그 다음 카드를 맨 뒤로 옮기는 작업을 반복합니다. 이 과정을 큐에 카드가 하나 남을 때까지 반복한 후, 남은 카드를 출력하면 정답이 됩니다.

문제 풀이에 사용될 자료구조는 선형 자료 구조 중에서도 양쪽 끝으로 데이터를 추가 혹은 삭제할 수 있는 Deque가 적합합니다. Kotlin Collection 에서는 ArrayDeque가 있기 때문에, 해당 Collection 을 이용해 문제를 풀어보기로 했습니다.

추가로, MutableList를 이용해 문제를 푸는 경우, 실제 채점 시에는 시간 초과가 발생합니다. 이는 MutableList가 기본적으로 링크드 리스트로 구현되기 때문인데요. 링크드 리스트는 각 노드들이 연결되어 있어서, 원소를 추가하거나 제거할 때마다 각 노드를 탐색하고 연결을 수정해야 합니다. 따라서 원소가 많아질수록 탐색 시간이 늘어나게 되어 실행 속도가 저하됩니다.