백준 9935 C++ (1) 썸네일형 리스트형 [백준/C++] 9935번 문자열 폭발 풀이 문제 해석 문제 풀이 우선 문자열은 100만 개라 O(N2)으로는 풀 수 없을 것 같았다. 문제에서 문자열을 찾아서 지워내면 되는 것이니 스택이나 정규식 풀이 방법이 먼저 떠올랐다. mirkovC4nizCC44 에서 C4를 추려내는 등의 과정을 고려했더니 문자열을 비교할 때 어디까지 겹치는 문자열을 보유했었는지 저장하도록 하였다. (전에 문자열 알고리즘 중에 이런 게 있었는데 까먹었다.ㅎㅎ) [로직] 문자열과 폭발 문자열을 한 문자씩 비교하며 정답 문자열에 추가한다. 문자가 같다면 폭발 문자열의 인덱스를 하나 증가시킨다. 다르다면 지금 인덱스를 스택에 넣어 저장하고 현재 문자열부터 다시 비교한다. 만약 인덱스가 폭발 문자열의 길이와 같다면 길이만큼 정답 문자열에서 제거한다. 만약 이전 인덱스 스택이 비었.. 이전 1 다음
