[Python] 백준, 1158(큐)

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

1158번: 요세푸스 문제

알고리즘 공부는 프로그래머스의 '어서 와 알고리즘은 처음이지?' 강좌와 'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책 두 가지로 기초를 다졌는데, 큐에 대해 소개된 내용은 스택과 크게 다르지 않다. 더욱이 collections의 deque모듈을 이용하면 스택과 큐 두 가지 동시에 사용할 수 있기 때문에 그 경계가 또한 모호해진다.

 

'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책에 소개된 큐의 개념 중에 링 버퍼라는 알고리즘이 있는데, 우선 그것부터 소개해보려 한다. 1158번을 처음 봤을 때는 당연히 링 버퍼인 줄 알았기에 조금 시간이 걸렸는데, 링 버퍼가 무엇인지에 대한 정확한 이해가 되었더라면 돌아가는 일은 없었을 것 같다.

 

# PYTHON CODE (1)

class FixedQueue:
    class Empty(Exception):
        pass
 
    class Full(Exception):
        pass
 
    def __init__(self, capacity):
        self.no = 0
        self.front = 0
        self.rear = 0
        self.capacity = capacity
        self.que = [None] * capacity
 
    def __len__(self):
        return self.no
 
    def is_empty(self):
        return self.no < 0
 
    def is_full(self):
        return self.no >= self.capacity
 
    def enque(self, data):
        if self.is_full:
            raise FixedQueue.Full
        self.que[self.rear] = data  # rear값에 데이터 삽입
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:  #  rear == capacity 인 경우엔 rear값을 초기화
            self.rear = 0
 
    def deque(self):
        if self.is_empty:
            raise FixedQueue.Empty
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x
 
    def peek(self):
        if self.is_empty:
            raise FixedQueue.Empty
        return self.que[self.front]
 
    def find(self, data):
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == data:
                return idx
        return -1
 
    def count(self, data):
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == data:
                c += 1
        return c
 
    def clear(self):
        self.no = self.front = self.rear = 0
 
    def dump(self):
        if self.is_empty:
            raise FixedQueue.Empty
        else:
            for i in range(self.no):
                idx = (i + self.front) % self.capacity
                print(self.que[idx], end='')

 

1158번 문제는 이렇게 거창한 알고리즘이 필요한 건 아니고, 인덱스를 설정하는 능력의 유무를 가려내는 문항인 것 같다.

 

 

# PYTHON CODE (2) - 1158

from collections import deque
 
s, n = map(int, input().split())
d = deque([i + 1 for i in range(s)])
answer = []
 
while len(d) != 0:
    for _ in range(n):
        x = d.popleft()
        d.append(x)
    answer.append(str(d.pop()))
 
print('<' + ', '.join(answer) + '>')

이런 구조는 처음 보는데, 알아두면 유용할 것 같다.

join은 '문자열'로 이루어진 구조에만 적용이 가능한 것 같아 에러를 방지하기 위헤 str함수를 추가하였다.

알고리즘은 생각외로 단순한데, 앞의 세 사람을 pop 하여 뒤로 append 한다. 이때 마지막으로 append 된 사람을 pop 해주어 n번째 사람을 제거해준다.

 

 

 

# PYTHON CODE (3) - 1158

s, n = map(int, input().split())
answer = []
list1 = [i + 1 for i in range(s)]
 
num = 0
for _ in range(s):
    num = (num + n - 1) % len(list1)
    answer.append(str(list1.pop(num)))
 
print('<%s>'%(', '.join(answer)))

구글링을 계속해봤는데, 'num = (num + n - 1) % len(list1)'이 한 줄이 해석이 좀 힘들더라.

 

나름 해석한 바 마찬가지로 원리는 단순한데, 본인 위치 인덱스인 num을 기준으로 오른쪽으로 두 칸 옆에 위치한 사람이 제거 대상이 된다. 따라서 num을 기준으로 계속 (n-1) 칸 옆에 있는 사람을 제거해주는 게 기본 목적이다(이때, n을 더해주는 것이 아니라 n-1을 더해주는 이유는 본인 위치 index가 기준이 되기 때문이다). len(list1)을 넘어갈 경우, 위에서 살펴본 링버퍼와 같이 IndexError가 나지 않도록 list길이로 나누어 계산한다.

 

인덱스로 장난 치는게 개인적으로 젤 어려운 것 같다. 마지막 줄은 기초문법인데, 까먹지 말자.