BOJ - 1158번 요세푸스 문제 (Python)

문제 출처: https://www.acmicpc.net/problem/1158

난이도

Silver 5

문제 풀이

링크드 리스트를 이용해서 문제를 풀어봤다. 링크드 특징을 이용해서 풀었고, 주의할 점은 노드를 삭제할 수록 size도 줄어드니깐 이에 대한 처리도 해줘야 했다 안해줘서 계속 에러 났음!

더 쉽게 풀 수 있는 방법들도 있는데 일부러 링크드 공부해서 풀어봤고 파이썬다운 풀이들은 밑에 참조해서 남겨놨다.

통과 코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            count += 1
            node = node.next

        return node

    def delete_Node(self, index):
        if index == 0:
            ans = self.head.data
            self.head = self.head.next
            return ans
        node = self.get_node(index - 1)
        ans = node.next.data
        node.next = node.next.next
        return ans


if __name__ == '__main__':
    N, K = map(int, input().split())
    ll = LinkedList(1)
    for i in range(2, N + 1):
        ll.append(i)
    arr = []
    idx = K - 1
    while ll.head is not None:
        idx %= N
        arr.append(ll.delete_Node(idx))
        idx += (K - 1)
        N -= 1
    print('<', end='')
    for i in range(len(arr) - 1):
        print(arr[i], end=', ')
    print(arr[len(arr) - 1], end='')
    print('>')

etc

N, K = map(int, input().split()) 
circular_list = [] 
answer = [] 
for i in range(N): 
	circular_list.append(i+1) 
  
popNum = 0

while len(circular_list) >0: 
    popNum = (popNum + (K-1)) % len(circular_list) 
    popElemnet = circular_list.pop(popNum) 
    answer.append(str(popElemnet)) 

print("<%s>" %(", ".join(answer)))

출처 블로그

N,K = map(int,input().split())
arr = [i for i in range(1,N+1)]    # 맨 처음에 원에 앉아있는 사람들

answer = []   # 제거된 사람들을 넣을 배열
num = 0  # 제거될 사람의 인덱스 번호

for t in range(N):
    num += K-1  
    if num >= len(arr):   # 한바퀴를 돌고 그다음으로 돌아올때를 대비해 값을 나머지로 바꿈  
        num = num%len(arr)
 
    answer.append(str(arr.pop(num)))
print("<",", ".join(answer)[:],">", sep='')

출처 블로그