문제
https://www.acmicpc.net/problem/5397
풀이
팁
-
처음에는 커서의 위치를 index로 두고 리스트 중간에 삽입, 삭제 연산을 하는 방법으로 풀었는데 그럼 O(N^2)이기 때문에 L의 길이 ≤ 1,000,000이어서 그런지 시간초과가 나서 스택 2개를 이용하는 방법으로 바꾸었다.
-
스택을 2개 이용해서 커서 왼쪽과 오른쪽을 구분한다.
push, pop으로만 구현할 수 있기 때문에 시간복잡도가 문자열의 각 character에 대해서는 O(1), 전체 문자열에 대해서는 O(N)로 시간초과가 나지 않는다.
-
커서 오른쪽을 큐로 구현해야하나 잠시 헷갈렸는데, 오른쪽 스택 원소를 왼쪽으로 이동시킬 경우 커서 오른쪽에 나중에 들어간 원소부터 pop 되어야하므로 오른쪽을 stack으로 구현해야 한다.
-
출력할 때에는 오른쪽 스택의 TOP이 왼쪽 스택에 이어지도록 스택을 붙여서 리턴하면 된다.
위 예시에서는 출력ABC로 B가 A 다음으로 오게 된다.
즉 오른쪽 스택 원소를 모두 왼쪽 스택으로 옮긴 후의 왼쪽 스택 결과와 같다.
코드
def solution(l):
left_stack = [] # 1)
right_stack = [] # 1)
for data in l:
if data == '<': # 2)
if left_stack:
right_stack.append(left_stack.pop())
elif data == '>': # 3)
if right_stack:
left_stack.append(right_stack.pop())
elif data == '-': # 4)
if left_stack:
left_stack.pop()
else: # 5)
left_stack.append(data)
left_stack.extend(reversed(right_stack))
return ''.join(left_stack)
number = int(input())
for _ in range(number):
l = list(input())
print(solution(l))
1) 스택 2개를 만들고 스택 두 개의 중간 지점을 커서로 간주한다.
2) '<': left_stack에서 pop한 요소를 right_stack으로 옮긴다. (left_stack이 비었으면 넘어간다)
3) '>': right_stack에서 pop한 요소를 left_stack으로 옮긴다. (right_stack이 비었으면 넘어간다)
4) '-': left_stack에서 pop (left_stack이 비었으면 넘어간다.)
5) 그 외: left_stack에 push
예시
