https://www.acmicpc.net/problem/5397
5397번: 키로거
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입
www.acmicpc.net
소스코드
풀이
★ 문제에서 커서에 대한 위치가 나올 때 2개의 스택을 활용하여 푸는 문제라고 생각했습니다. 이와 비슷한 문제들이 종종 있는 거 같아용
★ 입력받은 문자열을 돌면서 x가 괄호를 만나는지, 백스페이스를 만나는지 아니면 문자인지에 따라 수행이 달라지게 됩니다. X == '<'일 때 커서는 왼쪽으로 이동해야 합니다. 커서를 직접 이동시키는 것이 아니라 만들어둔 s2라는 스택에 s1의 마지막 원소를 빼서 추가해줍니다. 그러면 커서가 왼쪽으로 이동한 것과 같습니다.
ex) BP<
=> s1 = [B,P] x == '<'
=> s1 = [B], s2 = [P]
★ x가 '>'을 만날 때는 커서가 오른쪽으로 이동해야 하기 때문에 s2에 있는 마지막 원소를 s1에 추가해줍니다. 만약 x가 '-'을 만났을 경우에는 백스페이스 앞에 있는 문자를 삭제해줘야 하기 때문에 s1 스택이 비어있는지 확인하고, 비어있지 않으면 pop해줍니다. (비어있는 것을 확인하지 않으면 indexError 발생)
★ 마지막으로 반복문을 돌면서 구한 s1과 s2를 합쳐줘야 하는데, s1에 거꾸로 된 s2를 합쳐줘야 합니다. 그 이유는 s2가 만들어질 때 s1에서 빠져나온 원소들이 뒤에서부터 들어가기 때문에 실제로 입력 받는 값들이 반대의 순서로 되어 있기 때문입니다 !
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 3986번: 좋은 단어 (Python) (0) | 2023.06.03 |
|---|---|
| [백준 알고리즘] 17608번: 막대기 (Python) (0) | 2023.06.03 |
| [백준 알고리즘] 9935번: 문자열 폭발 (Python) (0) | 2023.06.02 |
| [백준 알고리즘] 2493번: 탑 (Python) (1) | 2023.06.02 |
| [백준 알고리즘] 17298번: 오큰수 (Python) (0) | 2023.06.02 |