표편집

문제

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

정확성 테스트케이스 하나를 통과 못했는데 뭘까.. 뭘까.. 혹시 제 코드를 보고 떠오르는 테스트케이스가 하나 있다면 공유해주세요 제발..🥺

update 시 코드 다시 올려놓겠습니다..!

접근 방식

링크드리스트를 구현할 수 있냐가 관건인 문제였다.

처음에 '링크드리스트로 풀어야겠다!'로 가기까지가 조금 걸렸다. 그런데 생각해보면:

• 리스트를 두고 pop이나 insert 연산을 하면 삭제 삽입 연산마다 추가로 O(n)만큼의 시간이 더 걸릴 것이기 때문에 극악의 효율성을 자랑할 것이다
• 그렇다면 그냥 리스트 내에서 o,x 표시 flag만 둔다면..? 삭제 삽입마다 고려할 게 많다.
• 결국, x인 행은 그냥 넘어갈 수 있도록 연결관계를 유동적으로 관리할 필요가 있다 👉 링크드리스트

노드는 클래스로 만들까 어쩔까 고민하다가 left pointer, right pointer를 둔 딕셔너리로 구현했다.

• up 연산: 현재 포인터만 이동하는 연산으로, 링크드리스트 left pointer를 타고가면 된다
• down 연산: 링크드리스트 right pointer를 타고가면 된다
• 삭제: 삭제된 인덱스는 따로 스택을 둬서 관리했다. 삭제노드의 left 노드, right 노드의 right pointer, left pointer를 다시 연결한다
• 삽입: 스택으로부터 pop한 노드의 left 노드, right 노드 pointer 연결 작업을 한다

코드

def initialize_linked_list(n):
    linked_list = [dict() for _ in range(n)]
    linked_list[0] = {'lp': -1, 'rp': 1} #-1은 end of list를 의미함
    for i in range(1, n-1):
        linked_list[i] = {'lp': i - 1, 'rp': i + 1}
    linked_list[n-1] = {'lp': n - 2, 'rp': -1}
    return linked_list

def solution(n, k, cmd):
    linked_list = initialize_linked_list(n)
    cp = k
    answer = ['O'] * n
    del_stack = []
    for x in cmd:
        if len(x) > 1:
            d, move = x.split()
            if d == 'U':
                for _ in range(int(move)): 
                    cp = linked_list[cp]['lp']
            elif d == 'D':
                for _ in range(int(move)): 
                    cp = linked_list[cp]['rp']
        else:
            if x == 'C':
                answer[cp] = 'X'
                del_stack.append(cp)
                left_idx = linked_list[cp]['lp']
                right_idx = linked_list[cp]['rp']
                if right_idx == -1: #cp == last node
                    linked_list[left_idx]['rp'] = -1
                    cp = left_idx
                else:    
                    linked_list[left_idx]['rp'] = right_idx
                    linked_list[right_idx]['lp'] = left_idx
                    cp = right_idx       
            else:
                new_idx = del_stack.pop()
                answer[new_idx] = 'O'
                left_idx = linked_list[new_idx]['lp']
                right_idx = linked_list[new_idx]['rp']
                linked_list[left_idx]['rp'] = new_idx
                linked_list[right_idx]['lp'] = new_idx
    return ''.join(answer)