알고리즘 분류 스택 자료구조 연결리스트
🔗 문제 출처 https://www.acmicpc.net/problem/1406
문제 유형이 스택임을 알았음에도 불구하고 문제 해결 방법을 생각해내기가 쉽지 않았다. 자료구조가 부족하다는 것을 느끼게 된 문제이다. 결국 마지막으로 제출한 정답코드는 구글링을 통해서 아이디어를 얻게 되었다.
이 문제의 포인트는
- 두 개의 스택을 활용
- 시간 초과를 염두
- 두 번째 리스트 거꾸로 출력
인 것 같다. 코드를 보면 다음과 같다.
📎 코드
python
import sys
word1 = list(sys.stdin.readline().strip())
word2 = []
for _ in range(int(sys.stdin.readline())):
li = sys.stdin.readline().split()
if li[0] == 'L' and word1:
word2.append(word1.pop())
elif li[0] == 'D' and word2:
word1.append(word2.pop())
elif li[0] == 'B' and word1:
word1.pop()
elif li[0] == 'P':
word1.append(li[1])
answer = word1+word2[::-1]
print(''.join(answer))📎 풀이
위에서 언급했던 것처럼 시간 제한이 0.3초로 다른 문제보다 빠듯하다는 것을 알 수 있다. 따라서 입력을 받을 때 input()이 아닌 stdin의 readline()을 활용한다. 참고로 readline()은 개행을 포함하기 때문에 '\n'을 없애주기 위해 strip() 혹은 rstrip()을 사용해야한다.
두 개의 스택을 두는 것은 커서의 위치를 고려하기 위함이다. 즉, 커서를 움직이기보다는 커서는 고정해두고 스택의 요소들을 움직이며 에디팅하는 로직이다.
여기서의 포인트는 두 번째 스택, 즉 커서의 오른쪽에 위치하는 리스트는 거꾸로 구성된다는 것이다. 파이썬은 스택을 제공하지 않기 때문에 리스트를 사용하여 풀어야하기 때문이다. 그렇다면 insert()함수를 사용하면 될 것 같다. 하지만 insert()함수의 시간복잡도는 O(n)이다. 제한시간을 고려하여 시간 복잡도인 append()를 사용하여 거꾸로 구성하는 것이 중요한 포인트이다.
만약 입력된 문자가 'L'이라면 커서 기준으로 왼쪽 값을 오른쪽 리스트으로 넘기면 된다. 따라서 왼쪽에서 pop()하여 오른쪽 리스트에 append() 해준다. 주의해야할 것은 문제의 조건도 조건이지만 pop()을 할 때 리스트가 비어있다면 예외가 발생한다. 따라서 리스트가 비어있지 않다는 조건을 달아준다.
입력 문자 'D'와 'B'도 마찬가지로 pop()할 대상 리스트의 empty여부를 확인해주고 로직을 실행한다.
'P'는 단순히 커서의 왼쪽에 값을 추가하면 되기 때문에 리스트의 empty여부를 확인할 필요 없이 append()해주면 된다.
왼쪽 리스트와 오른쪽 리스트를 합쳐 출력하면 되는데 이때 오른쪽 리스트를 거꾸로 출력해주는 것을 잊지말아야 한다.
