[프로그래머스] Linked list(연결 리스트), 효율성 개선 / 표편집

 

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

양방향 Linked List에 구현 로직이 동일한 것 같은데

왜 내 코드는 효율성 테스트를 통과하지 못하는 거지..?

비교해서 효율성 개선 방법 찾아내야겠다 ㅠㅠ

 

효율성 통과 코드

class Node:
    def __init__(self,data=None,prev=None,next=None):
        self.prev= prev
        self.data= data
        self.next= next
class DoubleLinkedList:
    def __init__(self,data=None):
        # for easy calculate at end set two dummy head_dummy and tail_dummy
        self.head = Node()
        self.tail = Node()
        # link two dummy
        self.head.next = self.tail
        self.tail.prev = self.head
        self.current_ptr = self.head
        self.delete_array = []


    def init_insert(self,data):
        new_node = Node(data)
        # get tail-1 node
        node = self.tail.prev
        node.next = new_node
        
        new_node.prev = node
        new_node.next = self.tail
        
        self.tail.prev = new_node
    
    def set_current_ptr(self, num):
        for i in range(num+1):
            self.current_ptr = self.current_ptr.next

    
    def c_instruction(self):
        self.before_ptr = self.current_ptr
        self.current_ptr = self.current_ptr.next
        if(self.current_ptr == self.tail):
            self.current_ptr = self.current_ptr.prev
            self.current_ptr = self.current_ptr.prev
        # delete!!
        self.delete_array.append(self.before_ptr)
        # modify linked list
        self.before_ptr.prev.next = self.before_ptr.next
        self.before_ptr.next.prev = self.before_ptr.prev
        
    def u_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.prev
    
    def d_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.next
    
    def z_instruction(self):
        node_to_z = self.delete_array.pop(-1)
        node_to_z.prev.next = node_to_z
        node_to_z.next.prev = node_to_z
    def return_del_array(self):
        to_return = []
        for i in range(len(self.delete_array)):
            to_return.append(self.delete_array[i].data)
        return to_return

            
def solution(n,k,cmd):
    answer_string = ["O"]*n
    my_list = DoubleLinkedList()
    for i in list(range(n)):
        my_list.init_insert(i)
    my_list.set_current_ptr(k)
    for instruction in cmd: 
        if instruction[0] == "U":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.u_instruction(move_cnt)
        elif instruction[0] == "D":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.d_instruction(move_cnt)
        elif instruction[0] == "C":
            my_list.c_instruction()
        elif instruction[0] == "Z":
            my_list.z_instruction()
    deleted_element = my_list.return_del_array()
    for element in deleted_element:
        answer_string[element] = "X"
    return ''.join(answer_string)

 

효율성 통과하지 못하는 코드

 

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = [i for i in range(n)] #비효율의 원인
    link_lst = LinkedList()
    
    for i in answer:
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    final = ["O" if x not in del_lst else "X" for x in answer] #비효율의 가장 큰 원인: O(N)
    final = ''.join(final)
    # print(final)
    return final

• 양방향 LinkedList까지 로직 참 좋았다 ! 
• input의 크기가 무지막지하게 크다는 사실을 기억해야 한다
• input 처리에 대한 단순한 코드때문에 => 눈덩이처럼 커진 비효율이,,,!!!!!!!
• input의 value는 사실 중요하지 않다. 서로가 '중복되지 않음'만 확인되면 된다.
  나는 처음에 각 Node를 생성하고 해당 노드의 value(Node.item)가 저장된 answer 리스트를 따로 생성했었다.
  그러나, integer로 채워진 answer 리스트를 임의로 생성할 필요가 없었다. 생성하면 무조건 비효율 문제가 발생하게 된다
  => answer 생성: O(N) + final 생성: O(N) = 2*O(N)
  이미 각 Node들의 item 값은 서로 다르기때문에 '중복되지 않음'의 속성이 반영되어 있다.
• 초반에 append한 각 Node의 value 값과 idx 값이 동일함을 이용하여 answer 리스트의 원소로 미리 "O"를 넣어둔다
• 마지막에 del_lst의 item값을 answer의 idx값으로 이용하여 answer 리스트에서 해당 idx의 값을 "X"로 바꾸어준다
  => final 리스트 따로 생성하지 않음! answer 리스트 내에서 변형.
  => O(N) + O(len(del_lst))
  => 이때 N보다 del_lst가 작으므로, N이 무지막지한 크기인 본 문제에서 효율성을 크게 높일 수 있다..!!

---

최종 효율성 통과 코드

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = ["O" for _ in range(n)] #효율 개선
    link_lst = LinkedList()
    
    for i in range(len(answer)):
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    for x in del_lst[1:]: #주의
        answer[x] = "X" #효율 개선
        
    answer = ''.join(answer)
    print(answer)
    return answer

 

 

---

너무 잘 정리된 LinkedList 개념

 

https://wayhome25.github.io/cs/2017/04/17/cs-19/

강의노트 18. 자료구조 - LinkedList (링크드 리스트) · 초보몽키의 개발공부로그

---

표 편집 솔루션에 대한 좋은 레퍼런스

 

https://latte-is-horse.tistory.com/329

[프로그래머스 lv3] 표 편집 (파이썬, 문자열, LinkedList)

https://life318.tistory.com/2

[프로그래머스] 표 편집(Double Linked List)