[백준] 큐 예제, 백준 1158번 요세푸스 문제(Josephus problem)

목표

저번 포스팅에서 배운 큐의 개념을 토대로 요세푸스 문제를 해결해보도록 하겠습니다.

 

1158번 : 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

요세푸스 문제란, N명의 사람들이 원형 탁자에 앉아있다고 했을 때, K번째 사람이 자리에서 일어나서 나간다고 생각하면 됩니다. 예를 들어, 5명이 앉아 있을 때 K=2라면 2번 사람이 일어나서 나가고 4번 사람이 일어나서 나가면 1, 3, 5번 사람이 앉아있겠죠? 그럼 여기서 3번이 나가는 것입니다. 앞에서부터 2의 배수번째 사람들이 나가는 거에요.

 

해당 문제를 큐로 구현해서 풀어보겠습니다. 문제 자체는 쉽지만, 반복문을 돌려서 해결하려면 N의 값이 커졌을 때 처리 시간이 오래 걸리게 됩니다. 이 부분에 대해서 코드를 보면서 생각해보겠습니다.

 

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

 

출력

입력에 따른 요세푸스 순열을 출력한다.

 

예제

입력 : 7 3 

출력 : <3, 6, 2, 7, 5, 1, 4>

 

문제 풀이

배운 것을 활용하기 위해서 큐 클래스를 활용해서 문제를 해결할 생각입니다.

참고 - [자료구조] 큐(Queue)란?

해서 큐 클래스를 만들고 큐 객체를 생성합니다.그리고 결과값을 담을 문자열을 하나 생성합니다. 생성된 큐 객체에 1부터 n까지 값을 enqueue하고 k번째 값을 문자열에 추가하고, k번째가 아닌 값은 큐의 뒤에다가 다시 쌓습니다. 이 과정을 큐의 길이가 1이 될때까지 반복합니다. 0이 아닌 1까지 반복하는 이유는 출력의 포맷을 맞추기 위해서 입니다. 양 끝에 꺽새와 쉼표를 넣어주기 위해서 1까지 하고 문자열에 마지막 값을 넣은 후에 닫는 꺽새를 추가해서 출력합니다. 

 

코드

▲ 간소화된 큐 클래스

먼저 큐 클래스입니다. 개념을 배울 때 작성했던 클래스보다 많이 간소화되었습니다. 

▲ 요세푸스 순열을 출력하는 과정

보시면 map 메소드를 활용해서 n, k 값을 한번에 입력받고 있습니다. 반복문을 돌면서 K번째 데이터를 문자열에 추가해주는 과정을 걸칠건데, 이 과정에서 인덱스로 쓰일 cnt라는 변수를 1로 선언했습니다. Q라는 객체를 생성해서 반복문을 통해서 1부터 n까지의 값을 큐에 삽입하는 과정입니다.

 

그리고 반복문을 돌면서 K번째 값은 dequeue하고, K번째가 아닌 값은 뒤에다 마저 쌓습니다. 그럼 결국 큐의 길이는 줄어들겠죠? 큐의 길이가 1이되면 반복문은 종료되고 해당 출력 포맷을 맞춘 뒤, 출력하면서 프로그램을 종료합니다.

 

문제점

사실 쉬운 문제라서 금방 풀고 지나갈거라고 생각했는데 뜻밖의 문제가 발생했습니다. 결과를 도출하는데까지는 얼마 걸리지 않았는데, 제출을 해보니 시간이 초과되었습니다.

 

시간을 단축하기 위해서, 우선 눈에 보이는 코드를 정리했습니다. dequeue 과정에서 큐의 길이가 0일 수가 없으니 조건문을 제거하고, front 함수도 쓰이지 않으니 제거해봤습니다.(되돌리기를 해서 사진엔 존재합니다.) 결과는 여전히 시간초과였습니다. 그래서 왜 그런지 곰곰히 생각해봤습니다.

문제 해결 과정에서 반복문을 돌리는데, N과 K의 범위가 5000까지 가능한 점이 원인이라고 결론을 내렸습니다. 그럼 5000개의 데이터를 가지고 조건문을 확인하고, 데이터를 삽입, 삭제하는 과정은 제가 봐도 오랜 시간이 걸릴 것이라고 생각했습니다. 더군다나 데이터를 진짜 삭제하는 것이 아닌 인덱스를 옮기는 것이기 때문에 메모리는 더더욱 커졌을 것입니다.

 

그래서 큐를 사용해서 문제를 해결하는 것은 가능하지만, 비효율적이라고 결론을 내렸습니다.

아니면 데이터를 실제로 삭제하는 방법을 거치는 것이 옳다고 생각합니다. 그래서 collections 모듈의 deque를 확인해보니, pop을 하고 길이를 확인해보면 실제로 길이가 줄어들어 있는 것을 확인할 수 있었습니다.

 

그리고 이 과정에서 pypy3과 python3의 차이점을 알았습니다. 둘의 큰 차이점은 컴파일 방식이 다르다는 것입니다.

짧게 설명하면 pypy3는 실행속도 측면에서 더 빠릅니다. 이번 예제처럼 반복문이 많은 코드에 적합합니다.

대신 python3는 메모리 관리측면에서 효율적입니다. 실제로 이번에 실행 시간을 줄이기 위해서 pypy3로 컴파일을 했는데 메모리가 무려 513952KB나 나왔습니다. 저번에 풀었던 괄호문제에 비하면 몇 배나 많은 수준입니다.

짧은 코드로 이런 상황을 초래할 수 있기 때문에 앞으로 코드를 작성할 때는 더욱 신중을 가할 필요가 있다는 점을 몸소 느꼈습니다.