[프로그래머스] 표 편집 - Python

🤔 문제

---

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

코딩테스트 연습 - 표 편집

😀 풀이

---

표 편집 문제에서는 특정 자료구조에 삽입, 삭제, 검색과 비슷한 행위들을 반복하여 수행해야 함을 알 수 있습니다. 또한 문제에서 효율성을 체크하게 되는데 이를 통해 적절한 자료구조를 떠올리고 이를 조건에 맞춰 구현해내는 것이 중요한 문제라고 생각했습니다.

 

가장 먼저 떠오른 자료구조는 기본적인 배열이어서 배열에 위와 같은 행위들을 했을 때 걸릴 시간복잡도를 생각해보았습니다. 만약 배열에 해당 열이 삭제되었는지 아닌지 여부를 0과 1을 사용해 저장하면 ( ex. [1, 1, 0, 0, 1] ) 시간복잡도는 아래와 같습니다.

1. Z 명령의 경우 배열에서 해당 Index를 0 -> 1로 바꿔주면 되기 때문에 O(1) 복잡도가 걸립니다.
  참고) Z 명령을 위해 삭제 시 스택에 열 정보를 넣어주어 가장 최근에 삭제한 열 정보를 찾아올 수 있도록 해야 합니다.

2. 커서를 움직이는 U, D 명령과 C 명령의 경우 최악의 경우 O(n)의 시간 복잡도가 걸리게 됩니다. 

 

따라서 n이 5,000 보다 작은 정확성 테스트는 통과할 수 있지만 효율성 테스트에서 무리가 있음을 예상해볼 수 있습니다.

 

그래서 사용한 자료구조가 링크드 리스트입니다. 본 문제에서 필요한 링크드 리스트를 구현하기 위해 따로 클래스를 만들 수도 있었지만 dict 자료구조를 이용하면 구현도 간편하고 특정 열에 대한 검색시간도 적게 만들 수 있습니다.

key 값은 열의 번호, value 값은 [ prev 열, next 열 ] 로 지정하면 특정 열에 접근하는 시간 복잡도도 O(1)이라 링크드 리스트보다 빠른 접근을 할 수 있습니다.

 

이러한 방법을 사용하면 U, D 명령은 최악의 경우 O(X)이고 C, Z 명령은 최악의 경우에도 O(1)이 걸리게 됩니다. 따라서 효율성 테스트를 성공적으로 통과할 수 있게 됩니다. 

 

💻 풀이 코드는 아래와 같습니다.

def solution(n, k, cmd):
    cur = k
    table = { i:[i - 1, i + 1] for i in range(n) }
    answer = ['O'] * n
    table[0] = [None, 1]
    table[n - 1] = [n - 2, None]
    stack = []
    for c in cmd:
        if c == "C":
            # 삭제
            answer[cur] = 'X'
            prev, next = table[cur]
            stack.append([prev, cur, next])
            if next == None:
                cur = table[cur][0]
            else:
                cur = table[cur][1]
            if prev == None:
                table[next][0] = None
            elif next == None:
                table[prev][1] = None
            else:
                table[prev][1] = next
                table[next][0] = prev

        elif c == "Z":
            # 복구
            prev, now, next = stack.pop()
            answer[now] = 'O'
            if prev == None:
                table[next][0] = now
            elif next == None:
                table[prev][1] = now
            else:
                table[next][0] = now
                table[prev][1] = now

        else:
            # 커서 이동
            c1, c2 = c.split(' ')
            c2 = int(c2)
            if c1 == 'D':
                for _ in range(c2):
                    cur = table[cur][1]
            else:
                for _ in range(c2):
                    cur = table[cur][0]
    return ''.join(answer)