[백준] 1406번 에디터 - Python(파이썬)

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

1406번: 에디터

 

문제

 

 

21.02.12 접근법

 

• 첫 번째 시도
  커서가 오른쪽에 위치하는 걸 디폴트 값으로 정하고 그 위치를 loca변수를 사용해 옮겨 다니고자 하였다.
  또한, 커서가 맨 처음 왼쪽으로 가게 되어 시작에 커서가 위치하였을 때는 front변수로 구분을 하고자 하였다.
  문자 삽입은 슬라이싱으로 코드를 구성하였지만, 시간 초과에서 걸려버렸다.
  슬라이싱이 원인인 거 같았다.

import sys

n=list(input())
M=int(input())
front=0
loca=len(n)-1

for i in range(M):
    com=sys.stdin.readline().split()

    if com[0]=='L':
        if loca==0:
            front=1
        else:
            loca-=1
    elif com[0]=='D':
        if loca==0:
            front=0
            loca+=1
        elif loca<len(n)-1:
            loca+=1
    elif com[0]=='B':
        try:
            if front==0:
                if loca==0:
                    front=1
                del n[loca]
                loca-=1
            
                
        except:
            pass
    elif com[0]=='P':
        new=[]
        if front==1:
            new.append(com[1])
            new+=n
        else:
            new=n[:loca+1]
            new.append(com[1])
            if(loca!=len(n)-1):
                new+=n[loca+1:]
        n=new
        loca+=1

for i in n:
    print(i,end='')

 

• 두 번째 시도
  시간을 줄이는 방법을 위해 검색을 한 결과, 알게 된 사실
  : 이 문제를 풀기 위해 시간복잡도가 O(1)이어야 하는데, 슬라이싱은 O(n)으로 시간복잡도가 더 높다.
  
  검색 전에 for문으로 push,pop도 해보았는데 for문으로 하게 되면 O(1)들이 n개 모여 O(n)이 되게 된다 한다.
  append와 pop은 시간복잡도가 O(1)로, 이것들과 list를 2개로 나눠서 사용하는 걸로 이 문제를 접근해야 하는 것이었다.

 

 

21.02.12 코드

import sys

left=list(input())
right=[]
M=int(input())

for i in range(M):
    com=sys.stdin.readline().split()

    if com[0]=='L':
        if left:
            right.append(left.pop())
    elif com[0]=='D':
        if right:
            left.append(right.pop())
    elif com[0]=='B':
        if left:
            left.pop()
    elif com[0]=='P':
        left.append(com[1])

right.reverse()
for i in left+right: 
    print(i,end='')

 

21.07.19 접근법

 

시간초과가 나서 보니 2월 12일에 했던 거와 똑같은 생각으로 똑같은 시도

발전한 점은 코드의 좀 더 통일성? 간소화?

 

 

21.07.19 코드

import sys

left_str=list(input())
right_str=[]

M=int(input())

for _ in range(M):
    cmd=sys.stdin.readline().strip().split()

    try:
        if cmd[0]=='L':
            right_str.append(left_str.pop())

        elif cmd[0]=='D':
            left_str.append(right_str.pop())

        elif cmd[0]=='B':
            left_str.pop()

        elif cmd[0]=='P':
            left_str.append(cmd[1])

    except:
        pass

ans=left_str+right_str[::-1]

for _ in ans:
    print(_, end='')