목록stack (1)

오늘 하루, develop

백준 9935번 - 문자열 폭발 (java)

💡 문제 링크https://www.acmicpc.net/problem/9935 💡 아이디어처음에는 슬라이딩 윈도우 형태로 풀이를 하였으나 시간 초과가 났다.슬라이딩 윈도우를 사용해도 부분문자열을 제거하는 과정 때문에 O(n)이 곱해져 시간 초과가 난다.결국 다른 풀이를 참고하였고, 스택을 사용해야 하는 것을 알았다. 1. 문자열의 문자를 하나씩 스택에 push 한다.2. 스택의 크기가 폭발 문자열의 길이 이상이 되고, 마지막 글자가 폭발 문자열의 마지막 글자와 일치한다면3. (폭발 문자열 길이만큼의)가장 위쪽의 문자들을 체크한다. 폭발 문자열과 일치하는지.     3-1. 일치하면 해당 문자들을 스택에서 제거한다.     3-2. 일치하지 않으면 1번으로 가서 다음 문자를 push한다.4. stack..
알고리즘 2024. 8. 5. 22:32
이전 Prev 1 Next 다음