[프로그래머스] Level 3 - 표 편집 (Python)

 

 

 

 

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

 

 

 

 

 

✅ Solution

• 그냥 리스트로 풀었다가 정확성만 통과하고 효율성은 통과를 못해서 구글링 해봤더니 링크드 리스트로 푸는 문제라는 걸 알았다. 너무 어려워
• linked_list는 딕셔너리로 선언하고, key는 인덱스, value는 해당 인덱스와 연결된 앞 인덱스와 뒷 인덱스로 이루어져 있다.
  • 0:[-1, 1], 1:[0, 2], 2:[1, 3]... 
• "U X", "D X"의 경우에는 단순하게 연결된 리스트를 X번 돌면서 확인하면 된다.
  • {0:[-1, 1], 1:[0, 2], 2:[1, 3], 3:[2, 4]} 일 때, k = 3, "U 2" 라면 인덱스가 2칸 앞에 있는 인덱스를 찾아야 하므로 3[0] -> 2 [0]을 통해 1이라는 것을 알 수 있다. 
  • 반대로 {0:[-1, 1], 1:[0, 2], 2:[1, 3], 3:[2, 4]} 일 때, k = 1, "D 2" 라면 1[1] -> 2[1]을 통해 3이라는 것을 알 수 있다.
• "C"의 경우, 먼저 해당 인덱스와 연결된 앞 인덱스, 뒷 인덱스를 받아와 prev, nxt에 저장한다. 그리고 해당 인덱스의 테이블 배열의 값을 "X"로 바꿔준다. 
• 그리고 nxt == n 즉, 지운 인덱스가 가장 마지막 행일 때는 앞에 있는 인덱스를 선택하고 만약 아니라면 다음 인덱스를 선택한다.
• 그다음에는 지운 인덱스의 앞 뒤에 있는 인덱스의 연결 정보를 바꿔주면 된다.
  • 만약 지운 행이 가장 앞쪽에 있는 행이라면 뒷 인덱스의 연결 정보만 바꿔준다.
  • 만약 지운 행이 가장 마지막에 있는 행이라면 앞 인덱스의 연결 정보만 바꿔준다.
  • 둘 다 아니라면 앞 뒤에 있는 인덱스의 연결 정보를 모두 바꿔준다.
• "Z"의 경우, pop()을 통해 가장 최근에 지워진 행의 정보를 가져와서 다시 앞 뒤 연결 정보를 바꿔주면 된다.
  • "C"와 마찬가지로 행의 위치를 고려해서 정보를 바꿔준다.

 

 

 

 

✅ Code

def solution(n, k, cmds):
    linked_list = {i: [i - 1, i + 1] for i in range(n)}
    table = ['O'] * n
    delete = []

    for cmd in cmds:
        cmd = cmd.split()

        if cmd[0] == 'D':
            for _ in range(int(cmd[1])):
                k = linked_list[k][1]

        elif cmd[0] == 'U':
            for _ in range(int(cmd[1])):
                k = linked_list[k][0]

        elif cmd[0] == 'C':
            prev, nxt = linked_list[k]
            table[k] = 'X'
            delete.append((prev, k, nxt))

            if nxt == n:
                k = linked_list[k][0]
            else:
                k = linked_list[k][1]

            if prev == -1:
                linked_list[nxt][0] = prev
            elif nxt == n:
                linked_list[prev][1] = nxt
            else:
                linked_list[prev][1] = nxt
                linked_list[nxt][0] = prev
        else:
            prev, now, nxt = delete.pop()
            table[now] = 'O'

            if prev == -1:
                linked_list[nxt][0] = now
            elif nxt == n:
                linked_list[prev][1] = now
            else:
                linked_list[prev][1] = now
                linked_list[nxt][0] = now

    return ''.join([x for x in table])