내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
에디터
ps:problems:boj:1406
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 에디터 ====== ===== 풀이 ===== * [[ps:problems:boj:5397]]과 거의 동일한 문제. * 현재 위치에서의 삽입과 삭제, 그리고 현재 위치를 왼쪽이나 오른쪽으로 한칸씩 이동하는 연산이 필요하다. * 이것들은 모두 링크드 리스트의 핵심 연산으로, 전부 O(1)에 가능하다. * 그러나 기본 라이브러리에 링크드리스트가 제공되지 않는 파이썬에서, 링크드리스트를 새로 구현하기는 귀찮고, 대신 2개의 스택을 이용해서 동일한 연산들을 똑같이 O(1)에 처리할 수 있다. [[ps:연결 리스트]] 참고. * m개의 명령어를 모두 O(1)에 처리 가능하므로 총 시간복잡도는 O(m). 문자열을 처음 읽어서 초기화하고 마지막에 출력하는 것까지 시간복잡도에 포함한다면 문자열의 길이인 O(n)을 추가해서, O(n+m)이 된다. ===== 코드 ===== <dkpr py> """Solution code for "BOJ 1406. 에디터". - Problem link: https://www.acmicpc.net/problem/1406 - Solution link: http://www.teferi.net/ps/problems/boj/1406 """ import sys def main(): text= sys.stdin.readline().rstrip() M = int(sys.stdin.readline()) left = list(text) right = [] for _ in range(M): match sys.stdin.readline().split(): case ['L']: if left: right.append(left.pop()) case ['D']: if right: left.append(right.pop()) case ['B']: if left: left.pop() case ['P', ch]: left.append(ch) print(''.join(left) + ''.join(reversed(right))) if __name__ == '__main__': main() </dkpr> {{tag>BOJ ps:problems:boj:실버_2}}
ps/problems/boj/1406.txt
· 마지막으로 수정됨: 2022/05/03 07:08 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로