[프로그래머스] 표편집 - 스택, 인덱스 리스트, 링크드 리스트

처음 문제를 보고, 삭제와 추가가 빈번하니 연결리스트를 사용해야 한다는 생각이 들었지만

댓글들을 보니 스택으로도 최적화하여 구현하면 충분히 구현 가능하다고 하여 연결리스트를 사용하지 않고 구현했다.

 

효율성 테스트를 통과하지 못했던 첫 코드와 개선 코드 두가지를 작성해보겠다

 

 

정확성만 통과한 초기버전 코드다.

dict 의 start,end 를 관리했고 이동할때 마다 이동할 행의 상태를 검사하며 이동했다.

초기 선언을 dict으로 하여 검색 간의 복잡도는 O(1) 이지만, 이동할때마다 반복이 돌며 행 상태를 검사해야하기 떄문에

그 부분에 시간을 많이 소요했다. 그래서 그 부분을 고치려고 생각해봤다.

def solution(n, k, cmd):
    
    q = {i: 'O' for i in range(n)}

    head = k
    start = 0
    end = len(q) -1
    out = []
    for i in cmd:
        if len(i) > 1:
            move = i.split(' ')
            cnt = 0
            move[1] = int(move[1])
            
            if move[0] == "U":
                while cnt < move[1] and head > start:
                    head-= 1
                    if q[head] != 'X':
                        cnt += 1
            elif move[0] == "D":
                while cnt < move[1] and head < end:
                    head += 1
                    if q[head] == 'O':
                        cnt += 1
        else:
            if i == "C":
                q[head] = 'X'
                out.append(head)
                while True:
                    head += 1
                    if head > end:
                        break
                    elif q[head] == 'O':
                        break
                
            elif i == "Z":
                try:
                    what = out.pop()
                    q[what] = 'O'
                    if what >= end:
                        end = what
                except IndexError as e:
                    pass

        if head < start:
            head = start
            
        elif head > end:
            while True:
                head = end -1
                end -= 1

                if end <= 0:
                    head = 0
                    end = 0
                    break
                    
                if q[head] == 'O':
                    break

    answer = ''
    for key, val in q.items():
        answer+=val
    return answer

 

 

시간 복잡도를 개선한 후 코드이다. 

행을 삭제하거나 복구하는 매커니즘은 똑같지만, 이동할떄 하나씩 탐색하는게 아니라

이동 가능한 행들의 정보를 담는 인덱스 리스트를 구성하여 일일히 탐색하는 것에서 개선했다.

 

예를 들어 

prev 는 [-1, 1, 2, 3],  next 는 [1, 2, 3, -1] 이런 식으로 구성해서 

2번 행이 선택되었을때 이전행은 prev[2], 다음행은 next[2] 이런 식이다.

 

행을 삭제했을땐 prev[next] = prev, next[prev] = next 

즉  1 -> 2 -> 3 일때 2를 지우면 3의 이전은 1로, 1의 다음은 3으로 이런 식이다.

자세한건 주석 참고하면 될 것 같다

def solution(n, k, cmd):
     
    head = k
    q = {i: 'O' for i in range(n)}
    out = []
    
    # 이동 가능한 행을 저장
    prev = [i - 1 for i in range(n)]
    next = [i + 1 for i in range(n)]
    next[n - 1] = -1  # 마지막 행의 다음 행은 없음
    
    for i in cmd:
        if len(i) > 1:
            move = i.split(' ')
            move[1] = int(move[1])
            
            if move[0] == "U":
                for _ in range(move[1]):
                    if prev[head] != -1:
                        head = prev[head]
                    else: break
                    
            elif move[0] == "D":
                for _ in range(move[1]):
                    if next[head] != -1:
                        head = next[head]
                    else: break
        else:
            if i == "C":
                q[head] = 'X'
                out.append((head,prev[head], next[head]))
                #  이전행의 다음행은 다음행으로 지정 (현재행이 원래 다음행인데 지웠으니까)
                if prev[head] != -1:  #처음 아닐때, 처음이면 그 전의 다음행이 없음
                    next[prev[head]] = next[head]
                # 다음행의 이전행은 이전행으로 지정 (현재행이 삭제되었으니까 그 전행으로)
                if  next[head] != -1: # 끝이 아닐때, 끝이면 다음행이 없으니까 다음행의 이전행을 설정할 수 없음
                    prev[next[head]] = prev[head]
                    
                temp = next[head] if next[head] != -1 else prev[head] # 지웠을때 다음행으로감, 근데 끝이면 그대로있음(그대로 있는게 이전으로 가는거임)
                head = temp if temp != -1 else head # 근데 만약 -1(처음) 이면 그대로 있음
                
            elif i == "Z": # 꺼내고 다시 연결해주는것, 이전행의 다음행을 지금행으로, 다음행의 이전행을 지금행으로
                try:
                    idx, prev_idx, next_idx = out.pop()
                    q[idx] = 'O'
                    if prev_idx != -1: # 꺼낸 원소가 처음이 아닐때
                        next[prev_idx] = idx
                    if next_idx != -1: # 꺼낸 원소가 끝이 아닐때
                        prev[next_idx] = idx
                except IndexError as err:
                    pass


    answer = ''
    for key, val in q.items():
        answer+=val
    return answer