[프로그래머스] 표 편집 / Python / 2021 카카오 채용연계형 인턴십

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

코딩테스트 연습 - 표 편집

---

Solution

def solution(n, k, cmds):
    nodes = {0: [n-1, 1]}
    for i in range(1, n):
        if i == n-1:
            nodes[i] = [i-1, 0]
        else:
            nodes[i] = [i-1, i+1]
            
    stack = []
    for cmd in cmds:
        if len(cmd) > 1:
            c, x = cmd.split(' ')
            cnt = 0
            # "D X"
            if c == 'D':
                while cnt < int(x):
                    k = nodes[k][1]
                    cnt += 1
            # "U X"
            else:
                while cnt < int(x):
                    k = nodes[k][0]
                    cnt += 1
        else:
            # "C"
            if cmd == 'C':
                nodes[nodes[k][0]][1] = nodes[k][1]
                nodes[nodes[k][1]][0] = nodes[k][0]
                stack.append([k, nodes[k]])
                tmp = nodes[k]
                del nodes[k]
                
                if tmp[1] == 0:
                    k = tmp[0]
                else:
                    k = tmp[1]
            # "Z"
            else:
                curr_node, val = stack.pop()
                prev_node, next_node = val
                nodes[curr_node] = [prev_node, next_node]
                nodes[prev_node][1] = curr_node
                nodes[next_node][0] = curr_node
    
    result = ''
    for i in range(n):
        if nodes.get(i) is None:
            result += 'X'
        else:
            result += 'O'
    
    return result

 

이 문제는 n이 1,000,000에 cmd가 200,000이므로 효율성까지 통과하려면 배열로는 어림도 없다. 그래서 처음 봤을 때 링크드리스트로 풀어야겠다는 생각을 했다.

 

그렇게 처음에는 노드 클래스를 만들고 링크드리스트를 구현해가며 풀었다. 근데 이렇게 풀면 고려해야할게 한 두개가 아니였다. 각 행을 삭제하거나 삽입할 때 해당 노드와 이전 노드, 다음 노드를 다 기억해야하고 현재 가리키고 있는 노드와 k값을 관리하기도 해야했다. 점점 코드가 길어지고 100줄이 넘어갔다. 뭐..맞기만하면 괜찮다고 생각했기때문에 제출했는데 아주 혼쭐이 났다. 여러 테스트케이스 만들어서 추가해봤는데 다 통과하기도 하고 문제를 못 찾겠어서 접근방식을 바꿔야겠다고 생각했다.

 

바꾼게 위의 풀이이다. 링크드리스트를 dict로 표현했다. 코드도 훨씬 간결하고 무엇보다 쉽게 구현할 수 있다. dict에서 한 원소가 노드를 가리키고 key는 행 번호를, value는 이전 노드의 번호와 다음 노드의 번호를 배열 형태로 담았다.

 

nodes = {0: [n-1, 1]}
for i in range(1, n):
    if i == n-1:
        nodes[i] = [i-1, 0]
    else:
        nodes[i] = [i-1, i+1]

 

이때, 첫 번째 노드의 이전 노드는 마지막 노드를 가리키고 마지막 노드의 다음 노드는 첫 번째 노드를 가리키는 원형 구조를 갖는 것에 주의한다. 아래와 같은 형태이다.

 

출처: https://aerocode.net/181

 

그리고 각 커맨드 별로 코드를 구현해보자. 먼저 D와 U이다. 이 둘은 현재 가리키고 있는 노드를 조작한다. 단순하게 k값을 가지고 숫자만 더해줬는데 이렇게 하면 dict에서 없는 노드를 참조할 수 있기 때문에 잘못된 방법이다.

dict로 구현한 링크드리스트에서는 이전 노드와 다음 노드의 번호를 알고 있기 때문에 그 번호를 타고타고 올라가거나 내려가면 된다.

 

if len(cmd) > 1:
    c, x = cmd.split(' ')
    cnt = 0
    if c == 'D':
        while cnt < int(x):
            k = nodes[k][1]
            cnt += 1
    else:
        while cnt < int(x):
            k = nodes[k][0]
            cnt += 1

 

위처럼 cnt변수를 하나 생성해서 현재 노드에서 x번 만큼 이동하면 된다. D일 경우 다음 노드로 이동하면 되고 U일 경우 이전 노드로 이동하면 된다.

예를 들어 예제에서 처음 k가 2이므로 두 번째 노드를 가리키고 있을 것이다. 다음 커맨드가 "D 2"일 경우 두 번째 노드에서부터 2번만 다음 노드로 가면된다.

 

다음 커맨드는 C이다. 해당 커맨드에서 핵심은 삭제이다. 링크드리스트에서 삭제 연산은 그렇게 어렵지 않다. 이전 노드의 next가 삭제될 노드의 다음 노드를 가리키게 하고, 다음 노드의 prev가 삭제될 노드의 이전 노드를 가리키게 하면 된다.

 

if cmd == 'C':
    nodes[nodes[k][0]][1] = nodes[k][1]
    nodes[nodes[k][1]][0] = nodes[k][0]
    stack.append([k, nodes[k]])
    tmp = nodes[k]
    del nodes[k]
    
    # 마지막 노드일 경우
    if tmp[1] == 0:
        k = tmp[0]
    else:
        k = tmp[1]

 

보기에는 좀 헷갈릴 수 있는데, nodes[k][0]은 해당 노드의 이전 노드를 가리킨다. 즉 nodes[nodes[k][0]][1]은 이전노드의 next라고 생각하면 된다. 여기에 nodes[k][1] 즉, 삭제되는 노드가 가리키던 다음 노드를 가리키게 한다.

반대로 nodes[nodes[k][1]][0] = nodes[k][0]은 다음 노드의 prev에 삭제되는 노드가 가리키던 이전 노드를 넣어주는 코드이다. 한번 이해하면 굉장히 쉬운 코드이다.

그렇게 삭제되는 노드의 행 번호 값과 이전 노드와 다음 노드 정보를 배열 형태로 stack에 넣어주고 del 연산자를 통해 링크드리스트에서 삭제해준다. tmp변수에 삭제되는 노드를 담는 것을 볼 수 있는데, 현재 가리키는 노드인 k를 관리해주기 위해서다. 마지막 노드가 삭제될 경우 삭제되는 노드의 이전 노드를 가리켜야 하므로 k에 tmp[0]을 담아주고 마지막 노드가 아닐 경우 삭제되는 노드의 다음 노드를 가리키게 한다.

 

마지막 커맨드는 Z이다.

stack에 있는 노드를 꺼내 원래 있던 자리에 넣어주기만 하면 된다.

 

curr_node, val = stack.pop()
prev_node, next_node = val
nodes[curr_node] = [prev_node, next_node]
nodes[prev_node][1] = curr_node
nodes[next_node][0] = curr_node

 

삽입할 때는 간단하다. 이전 노드의 next가 삽입되는 노드를 가리키게하고 다음 노드의 prev가 삽입되는 노드를 가리키게 하면 된다.