[Python3]프로그래머스_표 편집

문제출처:https://school.programmers.co.kr/learn/courses/30/lessons/81303

접근법

1. 본 문제는 효율성 테스트케이스들을 통과하기 위해서는 링크드 리스트(Linked List)를 활용해야 한다.

• 세그멘테이션과 이분탐색을 통해 푸는 방법도 있다고 하는데 정석적인 해답은 아니고 어떻게 접근하는지 모르겠다.

2. 각 노드들은 이전노드와 다음노드를 저장하고 있다. 각 노드는 dict의 키값으로 접근가능하고 값은 list의 형태로 [이전노드,다음노드]를 저장하고 있다.

3. "D","U","C","Z"에 대한 커맨드 수행

• "D" 또는 "U"의 경우 링크드 리스트의 이점으로 인해 해당 노드의 [이전노드,다음노드]의 값을 통해 반복적으로 수행할 수 있다.

• "C"의 경우 현재 노드의 이전 노드의 다음노드값(d[up][1])을 다음 노드로 지정하고 현재 노드의 다음노드의 이전노드값(d[down][0])을 이전 노드로 지정하면 현재 노드의 연결을 끊을 수 있다.

  • 이때 노드가 첫 노드거나 마지막 노드일 경우 이전 노드가 없거나 다음 노드가 없기 때문에 예외처리가 필요하다. ( 필자는 None 객체를 통해 처리하였다 )
  • 커서의 위치는 해당 노드가 삭제될 경우 바로 다음노드가 되지만 마지막 노드가 삭제됐을 경우는 커서의 위치는 이전노드가 된다.

• "Z"의 경우는 매우 쉽다. 처음에는 다양한 경우가 있다고 생각하였는데 문제에서 나왔듯이 최근에 삭제한 노드를 복구하기 때문에 경우는 해당 노드의 [이전노드값,다음노드값]은 모두 삭제되지 않은 유효한 노드값이 된다. 따라서 복구한 해당 노드의 이전노드의 다음노드값(d[up][1]) 을 해당 노드로 정하고 다음노드의 이전노드값(d[down][0])를 해당 노드로 정하면 다시 연결된다.

4. 처음에는 0~n-1까지 순회하며 삭제한 노드들이 담긴 trash 배열에 없다면 "X" 있다면 "O"를 answer에 이어 붙여 정답을 제출하였는데 이는 O(n) 만큼의 시간복잡도가 추가적으로 들어가기 때문에 시간 초과가 나는 테스트 케이스들이 생겼다. ( 이는 프로그래머스 질문하기 게시판을 통해 알게 되었다. )

• n의 크기이고 "O"로만 이루어진 배열에서 trash 배열에 담긴 노드번호들의 원소들만 "X"로 바꾸는 코드로 개선하였다.

코드

def solution(n, k, cmd):
    answer = [ "O" for i in range(n) ]
    d = dict()
    trash = []
    # Linked List
    for i in range(n):
        d[i] = [i-1,i+1]
    d[0][0],d[n-1][1] = None,None
	#
    for c in cmd:
        c_li = c.split(" ")
        op = c_li[0]
        if op == 'D':
            for i in range(int(c_li[1])):
                k = d[k][1]
        #  
        elif op == 'U':
            for i in range(int(c_li[1])):
                k = d[k][0]
        #    
        elif op == 'C':
            trash.append(k)
            up,down = d[k][0],d[k][1]
            if up  != None:
                d[up][1] = down
            if down != None:
                d[down][0] = up
            # 현재 행 위치 조정
            k = down if down else up
        #    
        else: # 'Z'
            z = trash.pop()
            up,down = d[z][0],d[z][1]
            if up != None:
                d[up][1] = z
            if down != None:
                d[down][0] = z       
    #    
    for t in trash:
        answer[t] = "X"   
    return "".join(answer)