사용자 도구

사이트 도구


ps:problems:boj:1406

에디터

ps
링크acmicpc.net/…
출처BOJ
문제 번호1406
문제명에디터
레벨실버 2
분류

스택

시간복잡도O(n+m)
인풋사이즈n<=100,000, m<=500,000
사용한 언어Python
제출기록37160KB / 328ms
최고기록208ms
해결날짜2022/04/29
태그

[라이] 리스트/배열/연결 리스트

풀이

  • 키로거과 거의 동일한 문제.
  • 현재 위치에서의 삽입과 삭제, 그리고 현재 위치를 왼쪽이나 오른쪽으로 한칸씩 이동하는 연산이 필요하다.
  • 이것들은 모두 링크드 리스트의 핵심 연산으로, 전부 O(1)에 가능하다.
  • 그러나 기본 라이브러리에 링크드리스트가 제공되지 않는 파이썬에서, 링크드리스트를 새로 구현하기는 귀찮고, 대신 2개의 스택을 이용해서 동일한 연산들을 똑같이 O(1)에 처리할 수 있다. 연결 리스트 (Linked List) 참고.
  • m개의 명령어를 모두 O(1)에 처리 가능하므로 총 시간복잡도는 O(m). 문자열을 처음 읽어서 초기화하고 마지막에 출력하는 것까지 시간복잡도에 포함한다면 문자열의 길이인 O(n)을 추가해서, O(n+m)이 된다.

코드

"""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()

토론

댓글을 입력하세요:
S᠎ D Z C᠎ K
 
ps/problems/boj/1406.txt · 마지막으로 수정됨: 2022/05/03 07:08 저자 teferi