[Python] 백준, 1406(스택)

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

1406번: 에디터

분명 어디선가 봤는데, 어딘지 기억이 나질 않는다. 아마 그때는 해결을 못했던거 같은데... 나 혹시 성장한걸까?

모든 문제가 그렇듯 문제 자체는 참 단순하지만, 어떻게 접근하느냐에 따라 그 복잡도가 가히 천차만별이다.

이번 문제도 거의 4가지 풀이를 구사했는데, 한번 들어가보자.

 

첫 풀이는 문제 분류가 스택이다보니, 당연히 스택으로 접근했다. 근데 리스트로 구현하는 스택은 원소를 중간에 삽입하는건 복잡도가 급격히 증가하는 걸로 알고 있어서 그 부분에 대한 해결이 우선 첫 관문이었다. 커서라는 개념 또한 자체 포인터를 하나 설정해 리스트의 인덱스를 따라가는 개념으로 설정해놨는데, 얼추 모양이 잡힌 후 찬찬히 지켜보니 본능적으로 이 풀이는 성공할 수 없다는게 느껴지더라.

 

두번째 풀이는 알고리즘을 처음 공부할 당시 스택에는 두가지 방식으로 구현할 수 있다고 배웠는데, 나머지 하나가 연결리스트이다. 연결 리스트같은 경우는 원소의 삽입과 제거가 용이하다는 장점이 있어 연결리스트를 이용한 스택의 구현을 목표로 코드를 작성해봤다.

 

 

# PYTHON CODE (1) - 연결리스트를 이용한 스택 구현

import sys
 
 
class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None
 
 
class LinkedStack:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.tail.next = None
        self.tail.prev = self.head
        self.head.next = self.tail
 
    def traverse(self):
        curr = self.head
        result = []
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
 
    def insertAfter(self, pre, newNode):
        curr = pre.next
        newNode.prev = pre
        newNode.next = curr
        pre.next = newNode
        curr.prev = newNode
        self.nodeCount += 1
        return True
 
    def insertBefore(self, curr, newNode):
        pre = curr.prev
        newNode.prev = pre
        newNode.next = curr
        pre.next = newNode
        curr.prev = newNode
        self.nodeCount += 1
        return True
 
    def popAfter(self, pre):
        curr = pre.next
        pre.next = curr.next
        curr.next.prev = pre
        self.nodeCount -= 1
        return True
 
    def popBefore(self, curr):
        pre1 = curr.prev
        pre2 = pre1.prev
        pre2.next = curr
        curr.prev = pre2
        self.nodeCount -= 1
        return True
 
    def push(self, newNode):
        curr = self.tail
        prev = curr.prev
        newNode.next = curr
        newNode.prev = prev
        curr.prev = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True
 
 
n = str(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline())
 
stk = LinkedStack()
 
for i in n:
    stk.push(Node(i))
 
curr = stk.tail
 
for _ in range(m):
    a = list(map(str, sys.stdin.readline().split()))
 
    if a[0] == 'L':
        if curr.prev.prev:
            curr = curr.prev
 
    elif a[0] == 'D':
        if curr != stk.tail:
            curr = curr.next
 
    elif a[0] == 'B':
        if curr.prev.prev:
            stk.popBefore(curr)
 
    else:
        stk.insertBefore(curr, Node(a[1]))
 
answer = ''
for i in stk.traverse():
    answer += i
 
print(answer)

결과는 성공이었다. 105줄이나 되는 코드를 작성했다는게 내심 굉장히 기뻤지만, 현실은 시간초과. 

근데 답은 잘 return해주기는 했다. 이 코드에서 시간을 더 절약하는건 무리라고 판단해 다른 방법을 생각해봤지만, 결국 구글링으로 힌트를 얻어 문제를 해결했다...

 

지금 문득 마지막 줄을 join함수로 처리했다면 조금은 효율이 좋았을까하는 생각이 든다.

(time 모듈을 슥 보고 둘의 실행 시간을 비교해봤는데 큰 차이는 없더라. 그래도 join 함수를 쓰는게 더 빠르긴 했다.)

 

 

# PYTHON CODE (2) - deque모듈

from sys import stdin
from collections import deque
 
list1 = list(stdin.readline().strip())
n = int(stdin.readline())
a, b = deque(list1), deque([])
 
for _ in range(n):
    k = list(stdin.readline().split())
 
    if k[0] == 'L':
        if not a:
            continue
        b.appendleft(a.pop())
 
    elif k[0] == 'D':
        if not b:
            continue
        a.append(b.popleft())
 
    elif k[0] == 'B':
        if not a:
            continue
        a.pop()
 
    else:
        a.append(k[-1])
 
print(''.join(list(a+b)))

 

# PYTHON CODE (3) - 리스트로 구현한 스택

import sys
 
a, b = list(sys.stdin.readline().strip()), []
n = int(sys.stdin.readline())
 
for _ in range(n):
    k = list(sys.stdin.readline().split())
    if k[0] == 'L' and a:
        b.append(a.pop())
    elif k[0] == 'D' and b:
        a.append(b.pop())
    elif k[0] == 'B' and a:
        a.pop()
    elif k[0] == 'P':
        a.append(k[-1])
 
print(''.join(a + b[::-1]))

백준 pypy3로 답안을 제출한 사람들 중 가장 빠른 실행시간을 보유한 분의 풀이와 거의 유사한데, 오히려 단순한 스택으로 어떻게 생각을 하느냐가 더 좋은 풀이를 가져온다는게 깔끔해서 좋다.

 

일반 리스트 메서드가 갖지 않는 popleft나 appendleft를 단순히 리스트를 역순으로 배열해주는 것으로 해결했다.

역시 세상은 넓고 똑똑한 사람들은 넘쳐난다...