[Python] 프로그래머스 / Level3 / 표 편집 (Linked List)

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

코딩테스트 연습 - 표 편집

 

2021 카카오 채용연계형 인턴십 3번으로 출제된 문제이다.

문제 이해 자체는 어렵지 않지만, 효율성 테스트를 통과하는 것이 어려워 난이도가 높다.

 

대놓고 첫째줄에 경고 문구가 적혀있다,, 😨

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

효율성 테스트를 통과하기 위해서 가장 중요한 것은 문제의 제한사항을 꼼꼼히 파악하는 것이다.

 

 

🤔 제한사항 분석

명령들이 담겨있는 리스트를 cmds로 이름짓고, 각 명령을 cmd라고 할 수 있다.

for cmd in cmds : ~ 로 풀이를 시작해야 한다는 것은 명백하다. 조건에 따르면 이는 O(10^4) time이 소요된다.

 

조건에서, n의 크기는 O(10^6)이기 때문에 cmd가 돌아가는 for 문 안에서 O(n)에 관한 동작을 다룬다면 ?

O(10^4) * O(10^6) = O(10^10) 으로 효율성 테스트를 절대 통과할 수 없게 된다..

 

for문 안에서는 O(log n)이나 O(1) 이 소요되는 동작이 반복되어야 한다는 것이다.

파이썬의 일반적인 자료구조 List로 solution 함수를 작성했다고 가정해보자.

 

List에서의 삭제 연산은 O(N) time이 소요된다. 중간에서 원소를 삭제했다고 가정했을 시, 그 뒤의 원소들을 한 칸씩 앞으로 끌어와야 하기 때문이다. 이 문제에서는 삭제 연산이 상당히 많이 일어날 수 있기 때문에 List는 풀이에 적절하지 않다는 것을 알 수 있다.

 

그래서 이 문제에서 사용하기 적절한 자료구조는 Linked List 이다.

Linked List는 insertion과 deletion 연산에서 O(1)의 효율성을 가지는 자료구조이기 때문이다.

next와 prev를 모두 다뤄야해서 정확히는 Double Linked List를 선택해야한다 !

 

🙄 여기서 중요한 의문이 생긴다. 

이 문제에서는 삭제 뿐만 아니라 탐색도 고려해야 하는데 ?? Up / Down 에서 탐색이 일어나고, 링크드 리스트에서의 탐색은 O(N) time이 소요되는데 ??

 

마지막 제한 사항이 이를 해소해준다. for cmd in cmds 는 최대 200,000번 반복된다. 여기서 계속 Up Down만 일어난다고 해도, 모든 X의 값을 합한 최대 값이 1,000,000이기 때문에 평균적인 X값은 5정도가 된다고 이해할 수 있다. 만약 극단적인 상황을 가정해 500,000이 연속 두 번 나온다 해도 효율성 테스트는 통과할 수 있을 것이다.

 

 

😊 소스 코드

파이썬에서 어떻게 링크드 리스트 코드를 작성해야할까 고민하다가, Dictionary 자료구조를 활용해보았다.

{ nodeNum : [prev, next] } 와 같은 구조로 설계하였고, 맨 HEAD는 { nodeNum : ['HEAD', next] }로 설정하였다.

TAIL도 같은 방식으로 설정해주었다.

 

def solution(n, k, cmds):
    answer = ['O'] * n
    # Double Linked List
    DLL = {i : [i-1,i+1] for i in range(n)}
    DLL[0][0] = 'HEAD'; DLL[n-1][1] = 'TAIL'
    stack = []
    
    for cmd in cmds:
        if cmd[0] == 'D':
            x = int(cmd[2:])
            for _ in range(x):
                k = DLL[k][1]
                
        elif cmd[0] == 'U':
            x = int(cmd[2:])
            for _ in range(x):
                k = DLL[k][0]
        
        elif cmd[0] == 'C':
            prev, next = DLL[k]
            answer[k] = 'X'

            if prev == 'HEAD':
                stack.append([k,prev,next])
                DLL[next][0] = 'HEAD'
                k = next
            
            elif next == 'TAIL':
                stack.append([k,prev,next]) # 삭제
                DLL[prev][1] = 'TAIL'
                k = prev    # 윗 행 선택
            
            else:
                stack.append([k,prev,next]) # 삭제
                DLL[prev][1] = next
                DLL[next][0] = prev
                k = next   # 아래 행 선택
                
        elif cmd[0] == 'Z':
            now, prev, next = stack.pop()
            answer[now] = 'O'
            
            if prev == 'HEAD':
                DLL[next][0] = now
            elif next == 'TAIL':
                DLL[prev][1] = now
            else:
                DLL[prev][1] = now
                DLL[next][0] = now          
    
    return ''.join(answer)