[Seop's의 코드풀이] 백준 5397 키로커 - Python

백준 5397 키로커

이번에 풀어볼 문제는 백준 5397번 키로커 라는 문제이다.
스택 알고리즘에 분류되어있고 solved.ac 랭크 실버3 정도의 문제이다.
문제는 다음과 같다.링크

내가 본 문제에서 중점적으로 본 것은 커서의 위치를 어떻게 컨트롤 하는지에 관련된 것이다.
커서의 위치를 기억하고 해당하는 위치에 비밀번호를 입력하고 삭제하게 된다면
굉장히 많은 시간을 낭비하게 될것이다.
Python list에서 insert와 특정위치의 pop의 시간복잡도는 O(N)이다.

문제 해결 아이디어

• 하나가 아닌 두개의 스택을 사용한다.(stack1, stack2)
• 알파벳이 나왔을 경우 stack1에 쌓는다.
• "-"가 나올경우 stack1에서 pop을 진행한다.
• "<" 가 나올경우 stack1에서 pop을 진행하고 stack2에 쌓는다.
• ">" 가 나올경우 stack2에서 pop을 진행하고 stack1에 쌓는다.
• 마지막으로 stack2에 있는 문자를 반전시킨후 stack1 뒤에 붙혀준다.

이렇게 진행을 했을경우 커서를 한번 옮길때 O(1) 두번만 진행되기 때문에 하나의 스택을 사용한 경우보다
훨씬 효율적이라고 생가된다.

전체 코드는 다음 Github 링크에 있습니다. 전체코드보기

질문과 피드백은 언제나 감사드립니다.