알고리즘

클래스

• 객체
• 생성자 
• 메소드
• self

single linked list

 

** join 은 배열요소값이 인트면 사용이 안된다.

오늘 강의에서 백준 1158 문제를 소개하길래 한 번 풀어봤습니다.
문제를 보니 왠지 배열로 가능할 것 같았습니다.
그러나 오늘 강의내용이 연결리스트 였기에 연결리스트로 만들어보았습니다.

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


class Linked_list:
    def __init__(self, count=1):
        self.head = Node(1)
        i = 1
        while i < count:
            self.append(i+1)
            i += 1

    def is_empty(self):
        if self.head == None:
            return True
        return False

    def append(self, data):
        cur = self.head
        while cur.next != self.head and cur.next != None:
            cur = cur.next
        cur.next = Node(data, self.head)

    def get_last_node(self):
        find_node = self.head
        while find_node.next != self.head:
            find_node = find_node.next
        return find_node

    def delete_node(self, node, step):
        if self.head.next == self.head:
            temp_node = self.head
            self.head = None
            return temp_node

        del_node = node

        count = 1
        while count < step:
            prev_node = del_node
            del_node = del_node.next
            count += 1

        if del_node == self.head:
            prev_node = self.get_last_node()
            self.head = del_node.next
            prev_node.next = self.head
        else:
            prev_node.next = del_node.next

        return del_node


def josephus_problem(n, k):
    linked_list = Linked_list(n)
    temp_node = linked_list.head
    del_arr = []

    temp_node = linked_list.delete_node(temp_node, k)
    del_arr.append(str(temp_node.data))
    while linked_list.is_empty() != True:
        temp_node = linked_list.delete_node(temp_node.next, k)
        del_arr.append(str(temp_node.data))

    return print(f'<{", ".join(del_arr)}>')
    
n, k = map(int, input().split())
josephus_problem(n, k)

분명 vscode에선 잘 작동하지만.. 백준에 답을 제출해보니 런타임 에러 (AttributeError)가 뜹니다.
이유를 찾아보려 했지만 아직 알아내지 못했습니다.

괜시리 정답을 맞췄다는 문구가 보고싶었던 저이기에
처음 문제를 봤을때 배열을 사용해서 풀 수 있을것같아서 다시 배열로 문제를 풀어보았습니다.

BOJ 1158
def josephus_problem(n, k):
    arr_max = []
    josephus_arr = []
    for arr in range(1, n+1):
        arr_max.append(arr)

    i = 0
    while len(arr_max):
        if len(arr_max) == 1:
            josephus_arr.append(str(arr_max.pop(0)))
            break

        i += k-1
        while not i < len(arr_max):
            i -= len(arr_max)

        josephus_arr.append(str(arr_max.pop(i)))
        if not i < len(arr_max):
            i = 0

    return print(f'<{", ".join(josephus_arr)}>')
    
n, k = map(int, input().split())
josephus_problem(n, k)

백준에서 맞았습니다!! 문구를 보니 마음이 편안합니다. 그러나 연결리스트로 만든건 왜 안되는지 아직 잘 모르겠습니다.
내일 한번 더 알아봐야겠습니다.