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

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

코딩테스트 연습 - 표 편집

 

Double Linked List를 활용하는 문제입니다. 

문제부터 간단하게 요약해서 설명해 보면, 다음과 같은 표에서 

아래의 instruction을 구현하는 문제입니다. 

행을 선택하는 U, D instruction과 삭제하는 C, 복구하는 Z instruction을 구현해야 합니다. 

 

solution(n, k, cmd)에 

n : 처음 표의 행 개수를 나타내는 정수
k : 처음에 선택된 행의 위치를 나타내는 정수
cmd : 수행한 명령어들이 담긴 문자열 배열

가 input으로 들어갈 때

 

모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교해 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 

"OXOOOXO" 의 형태로 return해야 합니다. 

 

<Solution 1-오답>

가장 간단하게 생각해보면, List를 사용해서 

list1 = 원소의 list list2 = 존재여부 list current_ptr = 현재의 커서 위치 modified_list = Z instruction 을 handling 하기 위해 삭제된 element들을 차례차례 저장

위와 같이 변수들을 두고, 매번 조회하는 형식으로 구현 할 수 있습니다. 

실제 구현은 아래와 같습니다. 

def solution(n, k, cmd):
    
    chart = list(range(n))
    ox_chart = [1 for _ in range(n)] # all exist
    current_ptr = k #just number
    modified = [] # to handling Z instruction
    
    for instruction in cmd: 

        if instruction[0] == "U":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            i = 0
            while(i < move_cnt):
                current_ptr-=1
                if (ox_chart[current_ptr]):
                    i+=1
            
        elif instruction[0] == "D":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            i = 0
            while(i < move_cnt):
                current_ptr+=1
                if (ox_chart[current_ptr]):
                    i+=1
            
        elif instruction[0] == "C":
            ox_chart[current_ptr] = 0
            modified.append(current_ptr)
            i = 0
            flag = 0
            before_ptr = current_ptr
            while(i < 1):
                if current_ptr == n-1:
                    break
                current_ptr+=1
                if (ox_chart[current_ptr]):
                    i+=1
                    flag = 1
            if flag == 0:
                # should go up
                j=0
                while(j < 1):
                    current_ptr-=1
                    if(ox_chart[current_ptr]):
                        j+=1
        elif instruction[0] == "Z":
            ox_chart[modified.pop(-1)] = 1
            
    answer = []
    for element in ox_chart:
        if element == 1:
            answer.append("O")
        else :
            answer.append("X")

    return ''.join(answer)

이와 같이 구현 할 시에 효용성 테스트 6~10을 통과 할 수 없습니다. 

 

어디에서 시간이 오래 걸리는지 생각해보면, 매번 U, D instruction을 수행할 시 list의 oxchart(존재여부를 확인하는 list) 를 조회해 특정한 index의 원소가 존재하는지 존재하지 않는지를 check하는 것을 알 수 있습니다.

 

<Solution 2-정답>

효용성 테스트를 통과 못하기 때문에 우리는 좀 더 좋은 방법을 생각해야 합니다. 

 

파이썬의 class로 Node를 여러개 만들어 이어 붙여주는 Double Linked List의 방식으로 구현하면, oxchart의 조회 없이 다음과 이전 Node를 알 수 있고, 삭제, 삭제한 Node 이어 붙이기 모두 쉽게 구현이 가능함을 알 수 있습니다. 

(Double Linked List에 대해서는 다른 Post에서 자세하게 다루고 업데이트 하도록 하겠습니다.)

 

실제 구현은 아래와 같습니다. 

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)