안녕하세요,
재재입니다.
BOJ 3111 검열 문제에 대한 풀이입니다.
BOJ 3111 검열
(1) 문제 설명
출처 : https://www.acmicpc.net/problem/3111
관련 : https://www.acmicpc.net/problem/9935
$$ A \leq 25, T \leq 300000, $$
을 만족하는 의 문자열 A와 T가 주어진다.
- T에 A가 없으면 알고리즘을 종료한다.
- T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
- T에 A가 없으면 알고리즘을 종료한다.
- T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
- 1번으로 돌아간다.
이때, 마지막에 남는 문자열을 출력하는 문제입니다.
(2) 풀이 힌트
문자열폭발 문제와 비슷한 맥락으로 문제를 해결하려고 하면 됩니다.
간략히 (문자열폭발) 문제를 설명하면,
왼쪽에서 오른쪽 방향으로 진행하면서 패턴과 매칭되는 문자열을 제거해주는 문제입니다.
이 문제의 풀이는,
스택에 문자열을 계속 추가해주고 패턴과 매칭되면,
스택에서 매칭된 문자들을 제거해주는 방식이고,
이때, 시간 복잡도는 $$ O(AT) $$ 입니다.
(3) 풀이 도출
이 문제는,
직관적으로 스택을 두개 사용하면 된다는 생각이 들었습니다.
(각 스택에) 남은 문자열에 대해서는 합치는 작업이 필요하고,
(왼쪽에서 시작하는) Left 스택에서 실패하거나,
Right 스택에서 실패했을 경우 합치고 다시 진행해야합니다.
이 다음에도 실패를 한다면, 종료하면 되는데요.
이때, 시간 복잡도도 $$ O(AT) $$
(4) 정답 코드
BOJ 3111 검열