[백준] 1406번 에디터

사용 언어 - Python3

1406번: 에디터 (실버2, 자료구조-스택)

문제 ★LG CNS 22년 상반기 코테랑 유사★

1406번: 에디터

 

정답

Stack 문제 + 시간복잡도 반영

내 정답은 시간복잡도를 반영하지 못하여 시간초과로 오답처리되었다. 테스트셋을 출력했을 땐 다 정답으로 나오긴 했다.

insert() 명령어도 시간복잡도가 O(N)으로 높기 때문에 사용할 수 없다.

list형태로 append와 pop만을 이용하면 O(1)으로 시간복잡도를 반영할 수 있다. -> 스택개념을 사용해야한다.

# 내 정답 - 시간초과
A = str(input()).lower() #입력 문자열
M = int(input()) #명령어 개수
C = len(A)+1 #커서 위치

order = []
for i in range(M):
    order.append(list(map(str,input().split())))


for i in range(M):
    if C < 0 :
        C = 0
    elif C >= len(A):
        C = len(A)
        
    if order[i] == ['L']:
        C -= 1
    elif order[i] == ['D']:
        C += 1
    elif order[i] == ['B']:
        if C <= 1 :
            A = A[C:]
            C -= 1
        else:
            C -= 1
            A = A[:C]+ A[C+1:]
    
    elif order[i][0] == 'P':
        A = A[:C]+ order[i][-1] + A[C:]
        C += 1
        
print(A)

(정답 풀이)

1. 왼쪽에 입력값을, 오른쪽에 빈 리스트를 만든다.

2. 첫 커서는 오른쪽 마지막에 있다.

3. L이 커서를 왼쪽으로 간다는 뜻은 반대방향으로 리스트를 만든다는 뜻이기 때문에 stack_l의 가장 오른쪽 원소부터 stack_r에 추가한다. stack_l은 가장 오른쪽 값을 계속 빼내기 때문에 커서의 위치는 자동으로 가장 오른쪽 마지막으로 리셋된다.

(예) stack_l=[a,b,c,d], stack_r=[] ~> L 3번 입력 ~> stack_l=[a], stack_r=[d,c,b]

새로운 리스트에 인덱스를 정반대로 저장해주면서, 커서는 새롭게 자동으로 가장 마지막 값으로 업데이트 되는 형태.

결론적으로 출력할 때만 stack_r을 reverse하면 되는 구조!

4. D는 L과 정반대 값이다. 다시 stack_r의 가장 오른쪽 원소(가장 마지막에 들어간 원소)를 빼서 stack_l로 append한다.

(예) stack_l=[a], stack_r=[d,c,b] ~> D 1번 입력 ~> stack_l=[a,b], stack_r=[d,c]

5. B는 stack_l의 가장 마지막 원소값을 제거한다. pop() 명령어 사용

(예) stack_l=[a,b], stack_r=[d,c] ~> B 1번 입력 ~> stack_l=[a], stack_r=[d,c]

6. P는 명령어의 두번째 값을 stack_l에 추가한다.

(예) stack_l=[a], stack_r=[d,c] ~> P x 입력 ~> stack_l=[a,x], stack_r=[d,c]

7. stack_l을 먼저 출력하고 stack_r을 reverse하여 list 형태로 출력하면 끝!

(예) [a,x,c,d]

8. pop 하는 리스트에 원소가 있어야 오류가 안나기 때문에 if문에서 "and stack_l" 처럼 확인해준다.

import sys
stack_l = list(input()) #입력문자열. list 형태여야 pop() 가능하기 때문
stack_r = [] #빈리스트
n = int(input()) #명령어 개수

for i in range(n):
    command = sys.stdin.readline().split() #명령어 입력
    
    #각 조건문 실행
    if command[0] == 'L' and stack_l:
        stack_r.append(stack_l.pop())
    elif command[0] == 'D' and stack_r:
        stack_l.append(stack_r.pop())
    elif command[0] == 'B' and stack_l:
        stack_l.pop()
    elif command[0] == 'P':
        stack_l.append(command[1])
   
print("".join(stack_l+list(reversed(stack_r))))

---

레퍼런스

• stack 사용한 정답 풀이

[백준] 에디터 1406번 파이썬 Python 자료구조

• 비슷한 풀이

[백준] 알고리즘 1406번 - python 풀이

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부