[프로그래머스] 표 편집 파이썬

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

코딩테스트 연습 - 표 편집

 

정확도는 범위가 적기 때문에 어렵지 않게 통과할 수 있다. 그냥 리스트로 insert, del만 해줘도 쉽게 통과할 수 있다.

하지만 효율성의 경우 시간초과가 많이 날 것이다.

나도 복구하는 것 때문에 시간초과가 계속 났다.

 

중간중간 insert과 delete가 많이 일어나기 때문에 연결리스트로 구현하였다.

또한 이전에 삭제한 노드를 복구하는 기능이 있기 때문에 위,아래로 이동하면서 삽입할 위치를 찾아야한다.

따라서 양방향 연결리스트를 사용하였다.

(나는 구현하다 보니 좌우가 아니라 위아래로 연결됐다고 생각하고 풀었다.)

 

처음에는 모든 노드를 0~n-1까지 다 연결된 리스트로 만들어서 시작한다.

 

삭제의 경우 현재 노드를 지워야하기 때문에 현재 노드의 위,아래 노드와 연결 시켜주자.

now.up.down = now.down

now.down.up = now.up

그리고 만약 지우려는 노드가 head나 tail이라면 head와 tail도 바꿔주자.

 

주의 할점은 노드를 지운다고해서 그 노드의 연결 정보를 지우지 말고 유지시켜주다. 이것을 이용하여 삽입 시 위치를 찾을 수 있다. 그리고 복구시 가장 최근의 데이터를 복구하기 때문에 삭제 정보는 스택에 저장하자.

 

다음은 위,아래 이동이다.

이는 그냥 x 만큼 연결리스트에서 이동 시켜주면된다.

문제에 범위를 벗어난 이동은 주어지지 않는다고 했기 때문에 그냥 up, down만 해주자.

 

마지막 복구이다.

이것 때문에 시간초과가 많이 났었다.

복구하려는 노드의 번호가 head보다 작다면 해당 노드를 head로 바꿔주고 연결시켜준다.

그게 아니라 노드 번호가 tail보다 크다면 해당 노드를 tail로 바꿔주고 연결시켜준다.

 

그게 아니라 사이에 있는 노드라면 삽입 위치를 찾아줘야한다.

 

처음에는 현재 점에서 head, tail에서 각각 이동시키면서 삽입할 위치를 탐색하였다. 당연히 최대 100만개의 노드가 있기 때문에 오래 걸려서 시간초과가 난다.

 

그래서 삭제한 노드의 연결정보를 활용했다.

해당 연결정보를 활용하여 위,아래로 탐색하면서 현재 살아있는 노드를 찾는다.

그리고 그 노드와 복구하려는 노드와 방향을 연결 시켜주면 된다.

노드가 살아있는지는 answer에 기록하였기 때문에 그것을 활용했다.

answer에 OOXXOO라고 되어 있고

3번 인덱스의 노드를 살린다고 한다면

위로가면 1번 인덱스의 노드를 찾을 것이고, 아래로는 4번 인덱스의 노드를 찾을 것이다.

그 다음 두 노드와 복구하려는 노드를 연결 시켜주면 된다.

 

def solution(n, k, cmds):
    answer = ['O'] * n
    head, tail, now = set_list(n, k)

    tmp = []
    for cmd in cmds:
        if cmd == 'C':
            answer[now.num] = 'X'
            tmp.append(now)
            if now.down and now.up:
                now.up.down = now.down
                now.down.up = now.up
                now = now.down
            elif not now.down:
                now.up.down = None
                now = now.up
                tail = now
            else:
                now.down.up = None
                now = now.down
                head = now
        elif cmd == 'Z':
            target = tmp.pop()
            if tail.num < target.num:
                tail.down = target
                target.up = tail
                tail = target
            elif head.num > target.num:
                head.up = target
                target.down = head
                head = target
            else:
                up = search_node(target,-1,answer)
                down = search_node(target,1,answer)
                
                target.up = up
                up.down = target
                target.down = down
                down.up = target

            answer[target.num] = 'O'
        else:
            order, x = cmd.split()
            x = int(x)
            if order == 'U':
                for _ in range(x):
                    now = now.up
            else:
                for _ in range(x):
                    now = now.down
    return ''.join(answer)

def search_node(node,dir,answer):
    while node and answer[node.num] == 'X':
        if dir == 1:
            node = node.down
        else:
            node = node.up
    return node

class Node(object):
    def __init__(self, num):
        self.num = num
        self.up = None
        self.down = None

def set_list(n, k):
    target = None

    head = None
    now = head
    for num in range(n):
        node = Node(num)
        if not now:
            head = node
            now = head
        else:
            now.down = node
            node.up = now
            now = now.down
        if num == k:
            target = now
    tail = now
    return head, tail, target