BAEKJOON #5397) 키로거 | Python

5397번: 키로거

 

💡아이디어

스택으로 구현합니다.

키보드 입력 커서를 기준으로 왼쪽 스택과 오른쪽 스택을 만듭니다.

스택을 만든 후, 입력된 문자열을 돌면서 백스페이스와 화살표에 따라 left_stack과 right_stack에 적절한 push, pop을 해줍니다.

 

💡전체 코드

전체 코드는 아래와 같습니다.

test_case = int(input())

for _ in range(test_case):
	left_stack = []
	right_stack = []
	data = input()[:-1]
	for char in data:
		if char == '<':
			if left_stack:
				right_stack.append(left_stack.pop())
		elif char == '>':
			if right_stack:
				left_stack.append(right_stack.pop())
		elif char == '-':
			if left_stack:
				left_stack.pop()
		else:
			left_stack.append(char)

	print(''.join(left_stack + right_stack))

 

 

❗️시간 초과 코드

처음에는 스택으로 구현하지 않고, 입력된 문자열을 돌면서 커서를 list의 index로 구현하였습니다. 하지만 아래 코드를 제출하니 시간 초과가 떴습니다. 그 이유는 위의 코드와 같이 push, pop연산은 list의 element로 바로 접근하지만, 아래와 같이 구현하게 되면 insert에서 리스트의 첫번째 원소부터 돌면서 삽입할 위치를 찾기 때문에 연산이 훨씬 느려집니다.

따라서 스택으로 구현해야 시간 초과가 발생하지 않을 수 있습니다.

def keylogger(key):
	stack = list()
	stack_idx = 0

	while len(key) > 0:
		char = key.pop(0)
		if char == '<':
			if stack_idx > 0:
				stack_idx -= 1
		elif char == '>':
			if stack_idx <= len(stack):
				stack_idx += 1
		elif char == '-':
			if len(stack) > 0:
				stack_idx -= 1
				stack.pop()
		else:
			stack.insert(stack_idx, char)
			stack_idx += 1

	print(''.join(stack))


if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		key = []
		key[:0] = input()[:-1]
		keylogger(key)