[프로그래머스 lv3] 표 편집, linked list

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

프로그래머스

 

 

첫 번째 시도

정확성만 다 맞았다

#Try 1 코드

def solution(n, k, cmd):
    answer = ["O"] * n
    c_list = []
    for cmd_now in cmd:
        if cmd_now[0] == "D":
            k = move(k, "D", int(cmd_now[2:]), answer)
        elif cmd_now[0] == "U":
            k = move(k, "U", int(cmd_now[2:]), answer)
        elif cmd_now[0] == "C":
            answer[k] = "X"
            c_list.append(k)
            if "O" in set(answer[k+1:]):
                k = move(k, "D", 1, answer)
            else:
                k = move(k, "U", 1, answer)
        elif cmd_now[0] == "Z":
            answer[c_list.pop()] = "O"
    answer = ''.join(answer)
    return answer

def move(now, d, mv, answer):
    i=0
    if d == "U":
        while(True):
            now-=1
            if answer[now] == "O":
                i+=1
            if i==mv:
                return now
    elif d == "D":
        while(True):
            now+=1
            if answer[now] == "O":
                i+=1
            if i==mv:
                return now

효율성은 0점이었다ㅠㅠ

초기 풀이 방식: U, D, C 명령은 O(n), Z 명령은 O(1)
• 효율성 테스트 케이스의 경우, 5 ≤ n ≤ 1,000,000 이라서 배열을 사용해서 해결하기에는 수행시간이 너무 오래 걸린다.

=> (양방향) 링크드 리스트 사용!

 

Linked List

Element들이 다른 곳에 흩뿌려져 있어서 서로 연결된 list.

단순히 특정 행의 상태만을 저장하는 것에서 벗어나, 리스트의 각 노드는 삭제되지 않은 이전/이후 노드에 대한 정보를 가진다. (정보 = 연결)

 

장점?
• U, D: 선택된 노드에서 X 번만 링크를 따라가면 되기 때문에 O(X)에 처리 가능
• C: 선택된 노드와 그 노드의 앞뒤로 연결된 노드들의 링크 정보만 변경해 주면 되기 때문에 O(1)에 처리 가능
• Z: 삭제된 노드 정보를 스택에 담아 두면 나중에 해당 노드에 O(1)에 접근하여 링크 정보를 복구해 줄 수 있기 때문에 O(1)에 처리 가능

링크드 리스트 사용해서 풀었을 때 효율성까지 다 맞았음!