1406번 - 에디터

💡 파이썬에서 연결리스트 문제는 연결리스트, deque, list로 풀 수 있다.

• 사실 이 문제를 처음 접했을 때는 연결리스트 문제라는 걸 바로 인지하지 못하였다.
• 파이썬에서는 연결리스트를 이용해서 문제를 푸는 것이 시간적인 부분에서 비효율 적이기 때문에 대부분 리스트나 deque를 통해서 접근한다.
• 문제에서는 시간 제한이 0.3초였기 때문에 리스트보다는 Deque를 적용시켜서 풀어보았다.

<시간 초과 코드>

import sys
from collections import deque

input = sys.stdin.readline

left = deque(input().rstrip())
right = deque()

M = int(input())

result = ''

for _ in range(M):

    command = input().rstrip()
    
    if command[0] == 'L' and left:
        right.append(left.pop())
    elif command[0] == 'D' and right:
        left.append(right.pop())
    elif command[0] == 'B' and left:
        left.pop()
    elif command[0] == 'P':
        left.append(command[2])
        
for i in left:
    result += ''.join(i)
    
for j in reversed(right):
    result += ''.join(j)
    
print(result)

• 위 코드는 시간 초과가 발생하였고, input도 readline으로 최적화 하였고, 논리도 맞았기 때문에 마지막 출력시 for문을 2번 돌린것이 문제라고 생각하였다.

<정답 코드>

import sys
from collections import deque

input = sys.stdin.readline

left = deque(input().rstrip())
right = deque()

M = int(input())

result = ''

for _ in range(M):

    command = input().rstrip()
    
    if command[0] == 'L' and left:
        right.append(left.pop())
    elif command[0] == 'D' and right:
        left.append(right.pop())
    elif command[0] == 'B' and left:
        left.pop()
    elif command[0] == 'P':
        left.append(command[2])
        
# 시간 단축을 위해 extend() 사용
reversedRight = reversed(right)
left.extend(reversedRight)

print(''.join(left))

• 위 문제는 커서의 위치가 계속해서 바뀌고 해당 원소 사이에 커서가 위치하기 때문에 처음에는 하나의 deque로 도전했지만, 원하는 index의 원소를 없애주는 메소드가 없었기 때문에 실패하였다. (List로는 가능 할 수 있을거 같다.)
• 따라서 left와 right 총 2개의 Deque를 두고, left의 맨 끝에 커서가 항상 위치하게 하여, 커서가 왼쪽으로 이동하면 left -> right로 커서가 오른쪽으로 이동하면 right -> left로 옮겨 주었고, B가 들어오면 항상 커서의 왼쪽이므로 left의 맨 마지막 원소를 지워주는 식으로 조건을 짜서 진행하였다.
• 마지막으로, extend()를 사용하여 left와 right의 역순의 값을 합쳐서 한번에 출력하여 시간초과를 해결하였다.

<Linked List를 직접 구현해서 푼 코드>

import sys

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self,val):
        new_Node = ListNode(val)
        
        if self.head is None:
            self.head = new_Node
        else:
            curr = self.head
            while curr.next != None:
                curr = curr.next
            curr.next = new_Node
            
    def get(self,idx):
        curr = self.head
        
        for i in range(idx):
            curr = curr.next
            
        return curr.val
    
    def insert(self, idx, val):
        
        new_Node = ListNode(val)
        curr = self.head
        
        if idx == 0:
            new_Node.next = curr
            self.head = new_Node
        else:
            for i in range(idx-1):
                curr = curr.next
                
            new_Node.next = curr.next
            curr.next = new_Node
        
    def remove(self,idx):

        if idx == 0:
            self.head = self.head.next
            return
    
        
        curr = self.head
        target = self.head
        
        for i in range(idx-1):
            target = target.next
        
        for j in range(idx):
            curr = curr.next
        
        
        target.next = curr.next
        
    def print_all(self):
        curr = self.head
        while curr is not None:
            print(curr.val, end="")
            curr = curr.next
        print()  
        
        
input = sys.stdin.readline

word = list(input().rstrip())

linkList = LinkedList()

for i in word:
    linkList.append(i)
    
M = int(input())

cursor = len(word)

for _ in range(M):
    
    command = list(input().rstrip())
    
    if len(command) > 1:
        linkList.insert(cursor,command[2])
        cursor += 1
    else:
        if command[0] == 'L' and cursor > 0:
            cursor -= 1
        elif command[0] == 'D' and cursor < len(word)+1:
            cursor += 1
        elif command[0] == 'B' and cursor > 0:
            linkList.remove(cursor)
            cursor -= 1

    print(cursor)
    linkList.print_all()
    
linkList.print_all()