[Boj/백준] 5397 Python

문제출처: https://www.acmicpc.net/problem/5397

5397번: 키로거

 

 

1. 문제 접근 방식

맨 처음에는 스택을 하나 두고 인덱스를 current 변수로 조정하면서 insert메소드로 삽입 pop으로 삭제하려고 했으나 시간초과가 발생했다. 그 후 스택 두개를 두고 lstack에 먼저 삽입한 다음에 >가 오면 lstack에 있는 원소를 rstack으로 append하고 <가 오면 rstack에 있는 원소를 lstack에 삽입하는 방식으로 풀었다.

 

 

2. 내가 푼 코드

<시간 초과 코드>

#시간 초과 코드
import sys

case = int(sys.stdin.readline())

for i in range(case):
    stack=[]
    current = 0
    x = sys.stdin.readline().strip()
    for i in x:
        if i != '-' and i != '<' and i != '>':
            stack.insert(current,i)
            current+=1
        elif i == '-':
            if stack:
                stack.pop()
        elif i == '<':
            if current > 0:
                current-=1
        elif i ==  '>':
            if current < len(stack):
                current += 1


    print(''.join(stack))

<새로 푼 코드>

import sys

case = int(sys.stdin.readline())

for i in range(case):
    lstack=[]
    rstack=[]
    x = sys.stdin.readline().strip()
    for i in x:
        if i != '-' and i != '<' and i != '>':
            lstack.append(i)
        elif i == '-':
            if lstack:
                lstack.pop()
        elif i == '<':
            if lstack:
                rstack.append(lstack.pop())
        elif i ==  '>':
            if rstack:
                lstack.append(rstack.pop())

    while rstack:
        lstack.append(rstack.pop())
    print(''.join(lstack))

 

 

3. 결과 및 느낀점

테스트 케이스가 많을 경우에는 처음 생각한 풀이처럼 풀면 시간초과가 발생할 확률이 크다.

스택 두 개를 사용해서 푸는 방법도 항상 염두해 두어야 할 것 같다.