[백준] 1406 에디터 (파이썬 python)

2022. 1. 24. 10:30· Algorithm/BOJ

 

 

문제 링크

 

 

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

 

1406번: 에디터

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수

www.acmicpc.net

 

 

문제

 

 

 

 

 

문제 풀이

 

 

insert, remove를 이용해 간단하게 풀려고 시도해봤지만

시간 초과가 나타났다. 문제에 나타난 입력 개수가 많기 때문에 시간을 잘 고려해야한다.

insert, remove 대신에 append, pop을 이용하면 시간복잡도를

O(N)에서 O(1)까지 줄일 수 있다.

아이디어를 찾기 어려워 나도 블로그를 많이 찾아봤는데 너무 좋은 아이디어가 있어 참고했다!

스택을 이용한 풀이로, st_left는 커서의 왼쪽, st_right는 커서의 오른쪽이 된다.

만약, L을 입력받아 커서가 왼쪽으로 이동할 경우 st_left의 마지막 요소가 pop되고 st_right에 append된다.

마지막에 st_left와 st_right을 extend를 통해 합쳐주는 과정을 거치게 된다.

이때, st_right는 append될 때 순서대로 쌓이게되므로 reversed를 이용하여 반대로 합쳐져야 한다.

1 2 3 4 5 6 /

의 리스트에서 L 1번이 이루어지면

1 2 3 4 5 / 6

L 1번이 다시 이루어지면

1 2 3 4 / 6 5

가 된다.

커서를 왼쪽으로 옮겼을 뿐, 순서가 바뀌면 안되므로 오른쪽 스택은 반대로 출력해야한다.

 

import sys
st_left = list(sys.stdin.readline().rstrip())
st_right = []

for _ in range(int(sys.stdin.readline())):
    command = list(sys.stdin.readline().split())

    if command[0] == 'L':
        if st_left:
            st_right.append(st_left.pop())
    elif command[0] == 'D':
        if st_right:
            st_left.append(st_right.pop())
    elif command[0] == 'B':
        if st_left:
            st_left.pop()
    else:
        st_left.append(command[1])

st_left.extend(reversed(st_right))
print(''.join(st_left))
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[백준] 1158 요세푸스 문제 (파이썬 python)  (0) 2022.01.25
[백준] 10824 네 수 (파이썬 python)  (0) 2022.01.24
[백준] 11655 ROT13 (파이썬 python)  (0) 2022.01.24
[백준] 10820 문자열 분석 (파이썬 python)  (0) 2022.01.23
[백준] 10809 알파벳 찾기 (파이썬 python)  (0) 2022.01.23
'Algorithm/BOJ' 카테고리의 다른 글
  • [백준] 1158 요세푸스 문제 (파이썬 python)
  • [백준] 10824 네 수 (파이썬 python)
  • [백준] 11655 ROT13 (파이썬 python)
  • [백준] 10820 문자열 분석 (파이썬 python)
YOONJELLY
YOONJELLY
YOONJELLY
JELLYJELLY
YOONJELLY
전체
오늘
어제
  • 분류 전체보기 (153)
    • Springboot (2)
    • Android (15)
    • Algorithm (126)
      • 개념 (8)
      • BOJ (91)
      • Programmers (15)
      • SWEA (4)
    • 경험_기록 (1)
    • RIM_TIP (4)
    • Github (2)
    • CS (1)
      • 운영체제 (1)
      • 컴퓨터네트워크 (0)
      • 정보처리기사 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • DFS
  • 딕셔너리
  • 알고리즘
  • 코딩테스트
  • 안드로이드
  • 다이나믹프로그래밍
  • DP
  • 백준
  • 자료구조
  • 소프티어
  • 완전탐색
  • 정렬
  • 큐
  • 프로그래머스
  • programmers
  • 이것이코딩테스트다
  • 파이썬
  • 그리디
  • kotlin
  • Android
  • 문자열
  • softeer
  • 이진탐색
  • SWEA
  • BFS
  • Python
  • 스택
  • BOJ
  • 코틀린
  • 액티비티컴포넌트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
YOONJELLY
[백준] 1406 에디터 (파이썬 python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.