[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현

문제

조세퍼스 문제는 다음과 같다.

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

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

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

해설

이 문제는 원형큐를 이용해서 풀 수 있을것 같네요. 첫번째 코드는 일반 큐를 사용하여 문제를 풀었고, 두번째 코드는 원형큐를 사용해서 문제를 풀었습니다.

제가 원형큐를 사용하여 문제를 푼 가장 큰 이유는 기본 Queue에서의 pop() 때문인데요. pop의 구현 내용을 보면 python list의 pop(0)을 호출한것을 확인하실 수 있습니다. pop(0)의 경우 가장 앞의 요소를 pop하는 대신에 전체 리스트를 전부 왼쪽으로 이동(shift)시키는 작업이 동반되는 O(N)의 작업입니다.  p.s.그냥 pop()의 경우 마지막 요소만 pop하기 때문에 O(1)입니다.

반면에 원형큐의 경우는 front와 rear를 사용하여 문제를 풀기 때문에 전체 배열을 shift하는 과정 없이 사용이 가능합니다.

* 백준 알고리즘 파이썬 코드가 시간초과 나는 경우

파이썬 자체가 실행속도가 느리다보니 다른 언어에서 시간초과가 나지 않는 코드를 파이썬으로 구현하였을떄 시간초과가 나는 경우가 있다고 합니다.

이런 경우에 pypy3를 언어로 설정하는 경우에 해결이 될 수 있습니다.

단, 알고리즘 자체의 시간 복잡도가 큰 경우에는 pypy3를 사용해도 시간초과가 나게 됩니다.

예를들어 아래 일반 Queue를 사용한 경우에는 pypy3를 사용해도 시간초과가 나지만 원형큐를 사용한 경우에는 pypy3를 사용하는 시간초과가 나지 않습니다.

코드 - Queue

class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0) if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if self.size() != 0 else -1
 
    def max(self):
        return max(self.queue)
 
n, m = map(int, input().split())
 
queue1 = Queue()
output_str = "<"
 
for i in range(1, n+1):
    queue1.push(i)
 
while(True):
    for i in range(m-1):
        queue1.push(queue1.pop())
 
    output_str = output_str + str(queue1.pop())
    if queue1.empty() == 1:
        break
    else:
        output_str = output_str + ", "
 
print(output_str + ">")
 

코드 - CircularQueue

class CircularQueue():
    def __init__(self, size):
        self.queue = [0 for x in range(size + 1)]
        self.front = 0
        self.rear = 0
        self.max_size = size
        self.list_size = size + 1
 
    def push(self, num):
        if (self.rear + 1) % self.list_size == self.front:
            return -1
        self.queue[self.rear] = num
        self.rear = (self.rear +1) % self.list_size
 
    def pop(self):
        if self.size() == 0:
            return -1
        temp = self.queue[self.front]
        self.front = (self.front + 1) % self.list_size
        return temp
 
    def size(self):
        if self.front == self.rear:
            return 0
        elif self.rear > self.front:
            return self.rear - self.front
        else:
            return self.max_size - (self.front - self.rear) + 1
 
    def empty(self):
        return 1 if self.front == self.rear else 0
 
    def max(self):
        return max(self.queue)
 
    def print(self):
        print(self.queue)
        print(self.front)
        print(self.rear)
 
n, m = map(int, input().split())
 
queue = CircularQueue(n)
 
output_str = "<"
 
for i in range(1, n+1):
    queue.push(i)
 
while(True):
    for i in range(m-1):
        queue.push(queue.pop())
 
    output_str = output_str + str(queue.pop())
    if queue.empty() == 1:
        break
    else:
        output_str = output_str + ", "
 
print(output_str + ">")