https://www.acmicpc.net/problem/3111
3111번: 검열
첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.
www.acmicpc.net
소스코드
풀이
★ 해당 문제를 푸시기 전에 다음 문제를 먼저 풀어보는 것을 추천드립니다 ! 스택 안에서 주어진 단어를 찾는 경우, 단어의 길이만큼 스택 위에서부터 찾는 방법을 익힐 수 있기 때문입니다 :)
https://www.acmicpc.net/problem/9935
9935번: 문자열 폭발
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모
www.acmicpc.net
★ 문제의 핵심은 주어진 t를 한번에 돌면서 주어진 조건에 맞는 경우들을 찾아내는 것입니다 ! 그러기 위해선 투포인터를 사용하여, 하나는 앞에서부터 다른 하나는 뒤에서부터 t를 읽으며 a와 같아지는 경우를 찾아냅니다 !
★ 주어진 알고리즘 중 2번과 4번을 구분하기 위해선 flag 변수를 사용하였습니다. flag 변수가 True일 경우 앞에서부터 가장 먼저 나오는 a를 찾아 제거해주고, flag 변수가 False일 경우 뒤에서부터 가장 먼저 나오는 a를 제거해줬습니다 !
★ end에서 단어 a를 찾는 경우에 주어진 단어를 거꾸로 뒤집는(reversed) 이유는 t의 요소들이 (뒤에서부터) 거꾸로 들어가기 때문에 단어 a도 거꾸로 뒤집어서 봐야하기 때문입니다 !
★ 마지막으로 start, end 두 스택에 남아있는 문자가 합쳐져 단어 a를 만드는 경우입니다 ! 이 경우엔 end에 있는 요소들을 start에 옮겨주면서, 위에서 했던 방식과 똑같이 단어 a와 같은 스택 안의 원소들을 찾아주시면 됩니다 !
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 25556번: 포스택 (Python) (4) | 2023.08.16 |
|---|---|
| [백준 알고리즘] 27497번: 알파벳 블록 (Python) (0) | 2023.08.16 |
| [백준 알고리즘] 16496번: 큰 수 만들기 (Python) (0) | 2023.08.11 |
| [백준 알고리즘] 9576번: 책 나눠주기 (Python) (0) | 2023.08.11 |
| [백준 알고리즘] 17952번: 과제는 끝나지 않아! (Python) (0) | 2023.08.10 |