[코딩 테스트 Java] 큐 ❷

스택 개념을 이해하고, 이를 바탕으로 스택의 ADT를 작성하고 구현해봅시다. 스택을 활용해 주어진 문제도 풀어봅시다.

[코딩 테스트 Java] 큐 ❷

이 글은 〈[되기] 코딩 테스트 합격자 되기(자바 편)〉에서 발췌했습니다.

골든래빗 출판사

김희성, 박경록 지음

큐 개념을 이해하고, 이를 바탕으로 ADT를 작성할 수 있습니다.

[코딩 테스트 Java] 스택 ❷ – 몸풀기 문제

지금까지 배운 내용을 활용해서 문제를 풀어보겠습니다. 여기서는 왜 큐를 사용하는지, 큐를 어떤 식으로 활용하는지에 집중하며 학습하기 바랍니다. 깃허브 코드를 확인해주세요.

문제 01 요세푸스 문제 ⭐️⭐️

저자 권장 시간_30분

권장 시간 복잡도_O(N*K)

출제_큐

정답 URL_https://github.com/retrogemHK/codingtest_java/blob/main/solution/15.java

N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

※ 이 문제는 유대인 역사가인 플라비우스 요세푸스가 만든 문제입니다.

1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.

없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution( ) 함수를 구현해주세요.

제약 조건

N과 K는 1이상 1000이하의 자연수입니다.

입출력의 예

01단계

N과 K에 실제 값을 넣고 요세푸스 문제를 손으로 풀어봅시다. N = 5, K = 2, 기준이 1인 경우를 예로 설명하겠습니다. N = 5이므로 이름표를 1~5로 붙이고 사람을 원형으로 배치합니다. 그리고 기준은 1입니다. 기준이 1이므로 ➊ K번째 사람은 2번 번호표를 가진 사람입니다. ➋ 이 사람을 제거하고 ➌ 다음 위치를 3으로 합니다.

02단계

같은 방식으로 ➍ 4번 번호표를 가진 사람을 제거하고 ➎ 다음 위치를 5로, ❻ 1번 번호표를 가진 사람을 제거하고 다음 위치를 3으로 합니다.

03단계

3 다음은 ➏ 다시 5이고, 이를 제거하면 3만 남습니다. ➐ 마지막은 3을 제거합니다.

문제 분석하고 풀기

문제를 다시 분석해봅시다. 사람들이 원형 테이블에 앉아 있다고 생각하고 1번부터 일정한 방향으로 한 사람씩 지목합니다. 사람이 사라진 후에도 지목 방향은 바뀌지 않습니다. 그리고 맨 마지막 사람을 지목한 다음에는 다시 처음으로 돌아갑니다. 선형 큐를 이용해 이 문제를 푸는 과정을 정리하면 다음과 같습니다. 그림은 N이 5이고 k가 3인 경우입니다.

※ 요세푸스 문제를 그림으로 나타낸 것을 보고 ‘원형 큐로 풀어야 되는 것 아닐까?’라고 생각하는 사람도 있을 것입니다. 하지만 코딩 테스트에서는 자바 컬렉션의 Queue 사용해도 메모리를 크게 낭비하지 않으므로 원형 큐를 사용하지 않아도 됩니다.

첫 번째 데이터부터 마지막 데이터까지 큐에 add합니다.

큐에서 k – 1번째까지의 데이터를 각각 front에서 poll하고 rear에 add합니다.

k번째 데이터를 poll하고 출력합니다.

큐에 더는 원소가 없을 때까지 과정 2~3을 반복합니다.

과정 2가 조금 이상하게 보일 수 있지만 그림으로 보면 왜 그렇게 하는지 쉽게 이해될 겁니다.

01단계

여기서 과정 2를 봅시다. k – 1번째 원소까지 poll하고 add하면 1, 2를 각각 poll하고 add하므로 큐 상으로는 2, 1, 5, 4, 3과 같이 2가 맨 뒤에 위치하게 됩니다. 그리고 이 과정을 통해 자연스럽게 poll할 데이터는 3이 됩니다. 제거해야 할 k번째 원소가 맨 앞으로 오게 되는 것이죠.

02단계

또 다시 4, 5를 각각 poll하고 add합니다. 마지막 데이터는 5가 되며, poll할 데이터는 1이됩니다.

같은 방법으로 계속해서 poll, add를 진행합니다. 설명은 같으므로 그림만 첨부하겠습니다.

03단계

04단계

05단계

Use a different Browser

import java.util.ArrayDeque;class Solution { private int solution(int N, int K) { // ❶ 1부터 N까지의 번호를 deque에 추가 ArrayDeque deque = new ArrayDeque<>(); for (int i = 1; i <= N; i++) { deque.addLast(i); } // ❷ deque에 하나의 요소가 남을 때까지 반복 while (deque.size() > 1) { // ❸ K번째 요소를 찾기 위해 앞에서부터 제거하고 뒤에 추가 for (int i = 0; i < K - 1; i++) { deque.addLast(deque.pollFirst()); } deque.pollFirst(); // ❹ K번째 요소 제거 } return deque.pollFirst(); // ❺ 마지막으로 남은 요소 반환 }}

❶ 사람 번호에 해당하는 1~N을 큐의 초깃값으로 넣습니다. ❷ 마지막 남은 사람의 번호를 알아야 하므로 큐의 원소가 1개일 때까지 반복문을 반복합니다. ❸ K – 1번째까지는 poll한 사람의 번호를 add하는 동작을 반복합니다. 왜냐하면 우리는 K번째 사람 번호를 제거해야 하기 때문입니다. ❹ K번째 사람 번호를 제거합니다. ❺ 마지막 남은 사람의 번호를 반환합니다.

시간 복잡도 분석하기

N은 전체 사람 수 K는 제거된 사람의 번호입니다. K – 1번 poll하고 1번 add하는 동작을 N번 반복하므로 최종 시간 복잡도는 O(N * K)입니다.

※ 이 문제는 세그먼트 트리라는 자료구조를 사용하여 풀면 O(NlogN)으로 시간 복잡도를 개선할 수 있습니다만 큐를 공부하는 차원에서 요세푸스 문제를 소개한 것이므로 큐를 사용하여 풀었습니다.

자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지

[되기] 코딩 테스트 합격자 되기(자바 편)

더 알아보기

저자 김희성

현 42dot 백엔드 개발자. 이전에는 삼성SDS에서 소프트웨어 개발자, 쿠팡에서 풀스택 개발자로 근무했다. 특히 삼성SDS 시절에는 사내 SW역량테스트 강사로 활약했다. 귀찮은 거 싫어하고 집에서 자는 게 가장 좋은 백엔드 개발자다. 어려운 문제와 맞닥뜨렸을 때 더욱 불타오르는 타입. 새벽 시간에 코드짜는 걸 좋아하며 주말에 밤새 코딩하는 일을 즐기는 ESTJ.

BFS DFS PYTHON 검색 그래프 깊이우선탐색 너비우선탐색 네이버 배달의민족 배민 버블정렬 빠른정렬 삼성 삼성전자 스택 알고리즘 알고리즘시험 우아한형제들 우형 이진트리 자료구조 자료구조시험 재귀호출 카카오 코딩테스트 코테 쿠팡 큐 탐색 트리 파이썬 프로그래머 프로그래머스 프로그래밍 프로그램

[코딩 테스트 Java] 큐 ❷

[코딩 테스트 Java] 스택 ❷ – 몸풀기 문제

문제 01 요세푸스 문제 ⭐️⭐️

[되기] 코딩 테스트 합격자 되기(자바 편)

📚 더 읽기