표 편집 문제 python - [프로그래머스/링크드리스트]

문제 내용 요약

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

입출력

8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]	"OOOOXOOO"
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]	"OOXOXOOO"

출처 : 프로그래머스

 

내가 푼 방식

문제 원리파악

"U", "D", "C", "Z" 4가지 방식의 조건으로 구현

1) "U" 일때

한 바퀴 이상 돌때는 나머지를 활용 Ex) U 15 이면, 15 % 총 크기(8) = 7

현재 위치보다 크거나 같을 때와 작을경우를 조건으로 현재위치를 구함

 

2) "D" 일때

한 바퀴 이상 돌때는 나머지를 활용 Ex) D 15 이면, 15 % 총 크기(8) = 7

[리스트의 총길이(8) - 현재위치(2) -1] = 5를 통해 이동가능한 거리를 구함, 이 경우 돌아감 없이 D로 5만큼 이동가능함 // 추가로 1을 빼줘야 리스트의 인덱스에 맞춰짐

이동 가능한 거리가 나머지보다 크거나 같을 경우와 작은 경우를 조건으로 현재위치를 구함

 

3) "C"일때

Stack 리스트

제거된 리스트를 따로 두어 현재 위치에 있는 [Position, 값]을 제거리스트로 이동 //  

 

4) "Z"일때

제거 리스트에 있는 값에서 가장 최신으로 들어온 값을 pop해 기존 리스트에 추가

 

이런 방식으로 풀었는데 정확성 테스트는 통과했지만...효율성에서 꽝이었다.

찾아보니 Insert가 중간에 끼워넣고 한칸씩 밀려나서 시간복잡도가 O(N)이 걸린다고 한다. 

파이썬 기본 연산자들의 시간 복잡도(Big-O) 정리

 

def solution(n, k, cmd):
    answer = ''
    
    start = 65
    val_list = []
    real_list = []
    position = k
    
    for i,v in enumerate(range(start, start+n)):
        val_list.append(chr(v))
        real_list.append(chr(v))
  

    # position 0-7
    # if u면 현재위치보다 움직이는 개 클 경우 총 크기 7 현재위치 3 / up 8 % 7 이동 / up 11 % 7 4 이동
    # 나머지 만큼 이동하는데 / 나머지 값이 클경우 : 나머지 - 현재위치
    
    # D에서도 총 크기 0~7 현 위치 5 / 총 길이에서 - 현재위치 일단 빼고
    # 7-5 보다 이동거리가 작거나 같으면 + / 7-5 보다 이동거리가 크면 현위치 5에서 이동4 / 이동 
    # 7 3 이동거리 14 % 8 = 6
    # 7 3 8-6
    
    # 5 % 8 = 5
    # 14 % 8 = 6
    # 나머지가 [총길이 - 현재 위치+1]보다 작거나 같으면 +
    
    # 현 위치가 2 [총길이 - 현재위치 - 1]  <- 이동가능한 거리
    # 이동가능한 거리보다 클경우
    # 이동가능한 거리가 5인데 이동해야하는 거리가 7이면 
    
    del_list = []
    
    # cmd 수정
    for a in cmd:
        if a[0] == "U":
            val = a.split(" ")
            val = int(val[-1])
                     
            if len(val_list) < val:
                val = val % len(val_list) 
            if position >= val:
                position = position - val
            elif position < val:
                val = val - position
                position = len(val_list) - val
        
        elif a[0] == "D":
            val = a.split(" ")
            val = int(val[-1])

            val = val % len(val_list) 
            
            if len(val_list) - position - 1 >= val:
                position = position + val
            elif len(val_list) - position - 1 < val:
                position = val - (len(val_list) - position - 1) -1
                
        elif a[0] == "C":
            
            if position == -1:
                continue
    
            if position == len(val_list) -1:
                del_list.append([position,val_list.pop(position)])
                position -= 1                
            else:        
                del_list.append([position,val_list.pop(position)])
        
        elif a[0] == "Z":
            if len(del_list) == 0:
                continue
                
#             if position == -1:
#                 position = 0
            
            pop_data = del_list.pop(-1)
        
            if pop_data[0] <= position:
                position += 1
                val_list.insert(pop_data[0], pop_data[1])
            else:
                if position == -1:
                    position = 0
                    val_list.insert(pop_data[0], pop_data[1])
                else:
                    val_list.insert(pop_data[0], pop_data[1])
                    
    for a in real_list:
        if a in val_list:
            answer += 'O'
        else:
            answer += 'X'
    
    return answer

 

 

다른 사람이 푼 방식 해석

다른사람 풀이를 찾아보니 링크드리스트를 활용해서 삭제/삽입의 시간복잡도를 O(1)로 해서 풀었다고 한다. 꼭 참고하자

 

링크드리스트 만드는법 방법

※ 링크드리스트의 종류중 '원형연결리스트'로 구현 

#1 노드 클래스
class Node:
	# 기본값
    def __init__(self):
        self.prev = -1 # 이전 노드 인덱스
        self.next = -1 # 다음 노드 인덱스

# n만큼 노드 생성
node_list = [Node() for _ in range(n)]

for i in range(n-1):
    node_list[i].next = i + 1 # 현재 노드에서 다음 노드의 인덱스 삽입
    node_list[i + 1].prev = i # i+1 번째 노드의 prev는 i

전체 코드 분석

from collections import deque

n = 8
k = 2
cmd = ["U 3"]

#1. 링크드리스트 초기화
node_list = [Node() for _ in range(n)] # 노드 리스트 생성

for i in range(n - 1):
    node_list[i].next = i + 1 # i 번째 노드의 next는 i+1
    node_list[i + 1].prev = i # i+1 번째 노드의 prev는 i
    

# [ (node.prev, node.next ), ....] 로 구성되어 있음

# 2. 삭제된 노드를 저장할 스택
del_stack = deque()


# 3. 명령어 처리
cur = k # 현재 가리키고 있는 노드의 인덱스

for c in cmd:

    if len(c) > 1:
        c, move_size = c.split(' ')
        move_size = int(move_size)
        print(move_size)
        
    # 원형 링크드 리스트다보니 순회하게 되어있음
    if c == "U":
        for i in range(move_size):
            cur = node_list[cur].prev
    elif c == "D":
        for i in range(move_size):
            cur = node_list[cur].next

elif c == "C":
            node_list[cur].is_delete = True # 현재 노드에 삭제 표시
            del_stack.append(cur) # 스택에 삭제된 노드 번호 추가
         
            # 링크드리스트 삭제 방법
            # 삭제 위치를 알면 삭제 시간복잡도가 o(1)로 줄어듬 <- 장점
            
            
            prev_node = node_list[cur].prev # 이전 노드 번호
            next_node = node_list[cur].next # 다음 노드 번호
            print(prev_node)
            print(next_node)
 
            if prev_node != -1: # 이전 노드가 있는 경우
                #이전노드의 next값을 삭제된 노드의 다음값으로 변경
                node_list[prev_node].next = next_node # 이전 노드의 next를 삭제된 노드가 가리키던 next로 교체
                print(node_list[prev_node].next)
                
            if next_node != -1: # 다음 노드가 있는 경우
                node_list[next_node].prev = prev_node # 다음 노드의 prev를 삭제된 노드가 가리키던 prev로 교체
                print(node_list[next_node].prev)
                cur = next_node # 가리키고 있는 노드를 next_node로 갱신
            
            else: # 만약 다음 노드가 없는 경우 현재 위치를 이전노드로 반환
                cur = prev_node

    elif c == "Z":
        # 데크의 오른쪽 값을 가져옴
        del_node = del_stack.pop()
        node_list[del_node].is_delete = False # 해당 노드의 is_delete = False로 변경

        prev_node = node_list[del_node].prev # 삭제된 노드의 이전 노드
        next_node = node_list[del_node].next # 삭제된 노드의 다음 노드
        
        
        if prev_node != -1: # 이전 노드가 -1이 아닌경우
            node_list[prev_node].next = del_node # 이전 노드의 next를 현재 노드로 지정
        if next_node != -1:
            node_list[next_node].prev = del_node # 다음 노드의 prev를 현재 노드로 지정