[백준/파이썬] 1406 : 에디터

 

https://www.acmicpc.net/problem/1406

1406번: 에디터

풀이 ✅

2년 전, 1년 전에도 도전했다가 어제 오늘 푼 문제이다!! 😍😍

2년 전, 1년 전에는 조금 무식한(?) 방법으로 풀었다.

import sys

input = sys.stdin.readline

MIIS = lambda: map(int, input().split())

arr = list(input().strip())

cursor = len(arr) # 커서는 문장 맨 뒤에 위치

N = int(input())

for i in range(N):
    command = input().split()

    if command[0] == 'P':
        arr = arr[:cursor] + [command[1]] + arr[cursor:]

        cursor += 1


    elif command[0] == 'L':
        if cursor == 0:
            continue

        cursor -= 1


    elif command[0] == 'D':
        if cursor == len(arr):
            continue

        cursor += 1

    elif command[0] == 'B':
        if cursor == 0:
            continue

        arr = arr[:cursor-1] + arr[cursor:]

        cursor -=1

print(''.join(arr))

배열을 하나만 만들었고, 커서 위치와 명령어에 따라서 배열을 계속 slice 했다. 계속 리스트를 새로 만들다보니 시간이 오래 걸렸다.

게시판의 글 중 하나를 보고 연결 리스트라는 걸 활용하면 된다는 걸 알게 됐다! 그러면 리스트를 새로 만들지 않아도 되고 시간 복잡도가 줄어든다고 했다.

그런데 자료구조, 문제 풀이를 안한지 오래 돼서 기억이 잘 안나서 공부했다. 그리고 뚝딱 뚝딱 만들었다....

그런데 ...... 연결 리스트가 어디에선가 엉켜버려서 해결하지 못했다... ㅠㅠ (코드는 더보기를 봐주시고, 혹시 어디가 잘못됐는지 알고 계시면 꼭 알려주세요. .... )

 

import sys


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0
        self.cursor = None

    def find(self, index):
        cnt = 0
        node = self.head

        if index < 0 or index > self.length:
            return None

        while cnt < index:
            node = node.next
            cnt += 1

        return node

    def set_cursor(self,index):
        self.cursor = self.find(index)

    def append(self, data):
        new_node = Node(data)
        self.length += 1

        if self.head is None: # 맨 처음
            new_node.prev = None
            self.head = new_node
            return

        current = self.head
        while current.next != None: # 끝까지 가서
            current = current.next # 추가

        current.next = new_node
        new_node.prev = current

    def insert(self, data):
        new_node = Node(data)

        if self.head == None:
            new_node.next = self.head
            self.head = new_node
            self.cursor = new_node
            return

        # before : cursor.prev -> cursor
        # after: cursor.prev -(1)-> new_node -(2)-> cursor
        
        if self.cursor == None:
            
        else:              
            if self.cursor.prev != None:
                self.cursor.prev.next = new_node
            new_node.prev = self.cursor.prev
            self.cursor.prev = new_node
            new_node.next = self.cursor

        self.length += 1


    def pop(self, index):
        cnt = 0
        node = self.head
        prev = None
        next = self.head.next if self.head else None

        if index < 0 or index >= self.length:
            return -1

        if index == 0:
            self.head = next
            self.length -= 1
            return

        while cnt < index:
            if node.next:
                prev = node
                node = next
                next = node.next
                cnt += 1
            else:
                break

        if index == cnt:
            prev.next = next
            self.length -= 1

    def __len__(self):
        return self.length

    def print_list(self):
        result=''
        node = self.head

        while node:
            result += node.data
            if node.next:
                node = node.next
            else:
                break
        print(result)
        return result

    def print_reverse(self):
        node = self.cursor
        result = ''

        while node:
            result = node.data + result
            if node.prev:
                node = node.prev
            else:
                break
        print(result)
        return result

# input = sys.stdin.readline
#
# MIIS = lambda: map(int, input().split())
#
# arr = list(input().strip())
#
# linkedList = LinkedList()
# for str in arr:
#     linkedList.append(str)

linkedList = LinkedList()

'''
linkedList.append('a')
linkedList.append('b')
linkedList.print_reverse()
linkedList.set_cursor(2)
linkedList.insert('c')
linkedList.print_list()
#linkedList.set_cursor(1)
linkedList.print_reverse()
'''

N = int(input())

# 커서는 문장 맨 뒤에 위치
cursor = len(arr)
linkedList.setCursor(len(arr))

# 명령어
for i in range(N):
    command = input().split()

    if command[0] == 'L':
        if cursor != 0 :
            cursor -= 1
    elif command[0] == 'D':
        if cursor != linkedList.length :
            cursor += 1
    elif command[0] == 'B':
        if linkedList.pop(cursor-1) != -1:
            cursor -= 1

    else:
        linkedList.insert(cursor, command[1])
        cursor+=1

linkedList.print_list()

 

친구의 도움으로.. deque를 사용하면 된다는 아이디어를 얻어서 이걸 이용해서 풀었다.

deque는 양방향 큐로, 앞 뒤 방향 모두에서 요소를 추가/제거할 수 있다.

커서 왼쪽 deque, 오른쪽 deque를 만들어 두고 커서의 움직임에 따라서 값을 제거/추가하는 것이다.

양끝에서 요소 추가/제거할 때 시간 복잡도는 O(1)이라서 문제의 제한 시간 내에 통과 가능하다!!

 

정답 코드 👩‍💻

import sys
from collections import deque
input  = sys.stdin.readline


cursor_left_arr = deque(list(input().strip()))
cursor_right_arr = deque()
N = int(input())

# 명령어
for i in range(N):
    command = input().split()

    if command[0] == 'L':
        if len(cursor_left_arr) > 0:
            tmp = cursor_left_arr.pop()
            cursor_right_arr.appendleft(tmp)

    elif command[0] == 'D':
        if len(cursor_right_arr) > 0 :
            tmp = cursor_right_arr.popleft()
            cursor_left_arr.append(tmp)

    elif command[0] == 'B':
        if len(cursor_left_arr) > 0:
            cursor_left_arr.pop()
    else:
       cursor_left_arr.append(command[1])

print(''.join(cursor_left_arr) + ''.join(cursor_right_arr))