[Programmers][Python]표 편집

https://programmers.co.kr/learn/courses/30/lessons/81303?language=python3

📌풀이

---

내가 쓴 풀이(실패)

• 리스트의 인덱스를 활용하여 구현
• C의 경우, O이 나올때까지 현재 위치에서 뒤로 밀다가 없으면 앞쪽에서 찾는 방식 활용
  • 사라진 인덱스는 trash에 저장
  • 해당 인덱스의 table값은 X로 변경
• Z의 경우, trash에 저장한 인덱스를 꺼내 table의 값을 O로 변경
• U, D의 경우, X인 경우를 배제하고 움직이는 횟수를 활용하여 구현
• 정확도는 통과하였으나, 효율성에서 5개의 테스트 케이스만 통과

def solution(n, k, cmd):
    table = ['O' for _ in range(n)]
    trash = []
    for c in cmd :
        if c == 'C':
            trash.append(k)
            table[k] = 'X'
            # k 위치 변경
            while k < n and table[k] == 'X' :
                k += 1
            if k == n:
                k -= 1
            while 0 <= k and table[k] == 'X':
                k -= 1

        elif c == 'Z':
            table[trash.pop()] = 'O'
        else:
            flag = 1 if c[0] == 'D' else 0
            move, cnt = int(c[2:]), 0
            while cnt < move :
                k = k+1 if flag else k-1
                if table[k] == 'O':
                    cnt += 1
                    
                
                
    return ''.join(table)

내가 쓴 풀이(성공)

• 링크드 리스트 활용
  • 딕셔너리의 key를 인덱스값으로, value를 [앞의 값, 뒤의 값] 의 쌍으로 구현
• C의 경우, 해당 인덱스를 trash에 저장
  • 결과값도 X로 변경
  • 앞의 노드와 뒤의 노드를 연결
  • 현재 노드가 맨 앞, 맨 뒤인 경우를 고려하며, k값도 맞춰서 이동
• Z의 경우, trash에서 pop
  • 결과값 O로 변경
  • 꺼내온 노드의 위치를 파악하여 사이에 넣고 연결
• U, D의 경우, 이전, 이후 값들을 보며 노드를 횟수만큼 이동

def solution(n, k, cmd):
    res = ['O' for _ in range(n)]
    linked_list = {i:[i-1,i+1] for i in range(n)}
    trash = []
    
    for c in cmd:
        now = c[0]
        if now == 'D':
            move = int(c[2:])
            for _ in range(move):
                k = linked_list[k][1]
        elif now == 'U':
            move = int(c[2:])
            for _ in range(move):
                k = linked_list[k][0]
        elif now == 'C':
            pre,nex = linked_list[k][0], linked_list[k][1]
            trash.append(k)
            res[k] = 'X'
            if pre >= 0:
                linked_list[pre][1] = nex
                
            if nex < n :
                linked_list[nex][0] = pre
                k = nex
            else :
                k = pre
                
        else :
            now = trash.pop()
            res[now] = 'O'
            pre, nex = linked_list[now][0], linked_list[now][1]
            if pre >= 0 :
                linked_list[pre][1] = now
                
            if nex < n:
                linked_list[nex][0] = now
                
    return ''.join(res)

📌후기

---

링크드 리스트를 쉽게 구현할 수 있는 방법을 알았던 문제였다. 문제를 해결하는 동안, 정말 많은 시간이 소요되었지만 링크드 리스트 활용법을 알게 되었다는 점은 상당히 만족스럽다. 이전에 링크드 리스트를 활용할 때는 객체를 직접 만들어 활용하였는데, 간단한 경우 딕셔너리를 통해 쉽게 만들 수 있다는 것을 알게 되었다! 효율성과 같은 문제에서 자주 활용할 수 있을 것이라고 생각한다.

카카오 테크 블로그의 풀이를 보면서, Fenwick Tree를 활용하여 문제를 해결할 수 있다는 것도 읽었는데, 아직 그 방법에 대해서는 잘 모르겠다. 한번 연구해 봐야 겠다!