[프로그래머스, 2021 카카오 인턴쉽] 표 편집 python

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

코딩테스트 연습 - 표 편집

 

 

1. 해결 방법

일반적인 리스트로 구현하면 효율성 문제를 통과하지 못한다. 따라서 딕셔너리를 통해 더블 링크드 리스트를 구현해줘야한다.

더블 링크드 리스트는 현재 노드의 값과 전후 정보를 갖고 있는 자료구조이다.

주의해서 봐야할 점은 명령어 Z와 명령어 C에서 연결 정보를 업데이트하는 방식을 주의해서 보길 바란다.

명령어별로 함수를 따로 만들어 주었다.

def up(cur, i, link_info):
    """ 
    명령어 'U i' 를 동작하는 함수 
    cur : 현재 위치
    i : 반복할 횟수
    link_info : 연결관계를 저장함 link_info[node] :[이전 노드의 번호, 다음 노드의 번호]
    """
    
    for _ in range(i):
        pre, post= link_info[cur]
        cur = pre
    return cur
    
def down(cur, i, link_info):
    """
    명령어 'D i' 를 동작하는 함수
    cur : 현재 위치
    i : 반복할 횟수
    link_info : 연결관계를 저장함 link_info[node] :[이전 노드의 번호, 다음 노드의 번호]
    """
    for _ in range(i):
        pre, post= link_info[cur]
        cur = post
    return cur

def recover(cur, status, trash, link_info):
    """
    명령어 Z를 수행하는 함수
    cur : 현재 위치
    status[i] : i번쨰 원소가 삭제 여부를 저장하는 함수 존재하면 1 삭제면 0
    trash : 삭제된 노드와 연결정보를 저장 / trash[node] : [이전 노드의 번호, 다음 노드의 번호]
    link_info : 연결관계를 저장함 / link_info[node] :[이전 노드의 번호, 다음 노드의 번호]
    """
    
    #가장 최근에 삭제된 원소를 불러온다.
    deleted, node_info = trash.popitem()
    
    #존재여부를 업데이트 시켜주고
    status[deleted] = 1
    pre, post = node_info
  	
    #연결 정보를 업데이트 해준다.
    link_info[deleted] = [pre, post]
    
    # 이전 노드의 연결정보 업데이트 만약 None이라면 복원된 노드가 맨 앞의 원소이므로 업데이트 X
    if pre != None:
        link_info[pre][1] = deleted
    
    # 이후 노드의 연결정보 업데이트 만약 None이라면 복원된 노드가 맨 뒤의 원소이므로 업데이트 X
    if post != None:
        link_info[post][0] = deleted 
    
    return

def delete(cur, status, trash, link_info):

    """
    명령어 C 를 수행하는 함수
    cur : 현재 위치
    status[i] : i번쨰 원소가 삭제 여부를 저장하는 함수 존재하면 1 삭제면 0
    trash : 삭제된 노드와 연결정보를 저장 / trash[node] : [이전 노드의 번호, 다음 노드의 번호]
    link_info : 연결관계를 저장함 / link_info[node] :[이전 노드의 번호, 다음 노드의 번호]
    """
	
    #현재 위치 삭제
    status[cur] = 0
    
    #쓰레기통에 삭제한 정보를 넣어 준다.
    pre, post = link_info[cur]
    trash[cur] = link_info.pop(cur)
    
    #만약 삭제된 노드가 마지막 노드였다면
    if post == None:
    	#삭제된 노드의 이전 노드가 마지막 노드로 업데이트
        link_info[pre][1] = None
        return pre
	
    #만약 삭제된 노드가 첫번쨰 노드였다면
    elif pre == None:
        #삭제된 노드의 다음 노드가 첫번째 노드로 업데이트
        link_info[post][0] = None
    else: # 중간에 있는 노드라면
	    #이전 노드와 다음 노드를 연결해준다.
        link_info[post][0] = pre 
        link_info[pre][1] = post
    return post

    
def solution(n, k, cmd):

    answer = ''
    status = [1 for i in range(n)]
    trash = {}
    link_info = {i:[i-1, i+1] for i in range(1,n-1)}
    link_info[0] = [None, 1]
    link_info[n-1] = [n-2, None]
    
    #커맨드에 따라 동작
    for c in cmd:
        command = c[0]
        if command == "U":
            i = int(c.split()[-1])
            k=up(k, i, link_info)
        elif command == "D":
            i = int(c.split()[-1])
            k=down(k, i, link_info)
        elif command == "C":
            k=delete(k, status, trash, link_info)
        else:
            recover(k, status, trash, link_info)
	
    #존재 여부를 이용해 답을 작성한다.
    answer = ''.join(['O' if i else 'X' for i in status ])
    return answer