백준 알고리즘: 1406번 에디터 (Python)

문제 정보

---

1406번: 에디터

 

 

핵심

---

일단 문자열을 리스트 형식으로 바꾸어서 커서의 위치를 인덱스로 지정하고, 해당 위치에서 insert, remove 작업을 통하여 문제를 해결하려고 하는 사람들이 많을것 같다고 생각했다(물론 나도 했다가 시간 초과)

어쩌면 당연했던게 문자열의 길이가 짧은것도 아니고, 많은 수정을 필요로 했기 때문에 삽입, 삭제의 O(n)번의 반복은 이 문제를 해결하는 올바른 방법은 아니었던 것 같다

리스트의 경우 인덱스를 알고있는 상태에서 해당 원소에 접근하는 것은 O(1)의 시간복잡도를 가지지만, 리스트의 중간 위치에 원소를 추가하거나 삭제하는 작업은 O(n)의 시간복잡도를 가지기 때문이었다

 

따라서 나는 삽입, 삭제를 고려하여 연결리스트를 활용하여 문제를 풀고자 하였고 연결리스트의 경우 삽입, 삭제시 다음 노드와의 연결을 끊고 새로 추가할 노드와의 연결을 설정해주기만 하면 되기 때문에 해당 방식으로 문제를 풀이하였다

다만, next 노드의 데이터만 가지고 있다면 커서를 왼쪽으로 이동시켰을 때 해당 노드의 정보를 알 수 없기 때문에 before와 next를 가지는 class node를 구성하여 문제를 풀이하였다

 

풀이

---

import sys

class node:
    def __init__(self, data, before=None, next=None):
        self.data = data
        self.before = before
        self.next = next

    def printdata(self):
        self = self.next
        while self.next:
            print(self.data, end='')
            self = self.next
        print(self.data, end='')

def sol():
    s = sys.stdin.readline().strip()
    _ = sys.stdin.readline()
    head = node(' ')
    cur = head

    # data add
    for i in range(0, len(s)):
        nextnode = node(s[i])
        cur.next = nextnode
        nextnode.before = cur
        cur = nextnode

    # command
    command = sys.stdin.read().split('\n')
    for com in command:
        if 'L' in com:
            if cur.before:
                cur = cur.before
        elif 'D' in com:
            if cur.next:
                cur = cur.next
        elif 'B' in com:
            if cur.data != ' ':
                cur.before.next = cur.next
                if cur.next:
                    cur.next.before = cur.before
                cur = cur.before
        elif 'P' in com:
            newnode = node(com[2])
            newnode.before = cur
            newnode.next = cur.next
            if cur.next:
                newnode.next.before = newnode
            cur.next = newnode
            cur = newnode
    head.printdata()

sol()

해당 코드를 보면, 처음에 head를 빈 공간으로 두고 데이터를 삽입하였는데 그 이유는 커서의 경우

위 그림과 같이 문자열의 길이보다 1개 더 많은 경우의 수를 가지는데, 연결리스트로 풀이하다 보니 a, b, c 총 3개의 노드로는 a의 앞인 1번 위치를 표현하면 c의 뒤인 4번 위치를 표현하는 것이 불가능하고

또 4번 위치를 표현하면 1번 위치를 표현하는 것이 불가능하기 때문이다

우리는 커서를 대고 문자를 삽입할 때 위 4개의 위치를 고려했어야 했기 때문에 a 앞에 공백을 두어서 노드가 c에 위치할때 4번 위치에 커서가 있다고 가정하고(해당 문자의 뒤) a 앞에 있는 공백에 위치할 때 1번 위치에 커서가 있다고 가정하는 과정을 통하여

해당 문제를 해결할 수 있었던 것 같다

 

고찰

---

사실 풀이 후 나의 풀이가 완벽하다고 느끼진 않았기 때문에 다른 사람의 풀이를 보았는데

이렇게도 풀이할 수 있구나.. 라는 생각을 하였다

커서를 기준으로 왼쪽과 오른쪽 문자열을 나누어서 풀이하는 것을 보았는데, 단순 리스트의 끝에서 삽입과 삭제가 이루어지는 것은 O(1)의 시간복잡도가 발생하기 때문에 굳이 연결리스트를 활용하지 않아도 풀이할 수 있구나.. 더 효율적인 풀이가 이런것이구나 하는 생각을 하였고

해당 풀이로 다시 한번 풀이해 보았다

import sys

def sol():
    left = list(input())
    right = []
    com = sys.stdin.read().splitlines()
    for c in com:
        if c[0] == 'L':
            if len(left) > 0:
                right.append(left.pop())
        elif c[0] == 'D':
            if len(right) > 0:
                left.append(right.pop())
        elif c[0] == 'B':
            if len(left) > 0:
                left.pop()
        elif c[0] == 'P':
            left.append(c[-1])

    print(''.join(map(str, left)), end='')
    print(''.join(reversed(right)))

sol()

 

훨씬 간결한 풀이가 완성된 것 같다

left 리스트에는 커서 기준 왼쪽의 문자열을 나열하고, right 리스트에는 커서 기준 오른쪽의 문자열을 나열한다

커서를 왼쪽으로 이동시키면, 왼쪽 리스트의 마지막 요소를 pop 하여 오른쪽 리스트의 마지막 요소에 집어넣고

오른쪽으로 이동시키면 반대로 오른쪽 리스트의 마지막 요소를 왼쪽 리스트의 마지막 요소에 집어넣는다

 

마지막으로는 오른쪽 리스트는 커서를 기준으로 리스트의 끝 요소가 커서의 바로 오른쪽 요소이므로

반전된 리스트를 출력하면 문자열이 완성이 되는 것이다

 

참조

---

GitHub - dduneon/CodingTestPy

문제를 풀이하고, 해당 문제의 소스코드를 깃허브에 업로드하려고 한다

필요하다면 이곳을 참고하면 좋을것 같다