문제 백준 5052번 풀이 문자열 $ A $가 다른 문자열의 접두사인지 빠르게 확인해야 합니다. 입력 받은 전화번호를 모두 정렬해봅시다. 911 97625999 91125426 이 케이스를 정렬하면 911 91125426 97625999 이렇게 됩니다. 여기서 관찰할 수 있는 것은, 문자열 $ A $가 임의의 문자열 $ B $의 접두사가 된다면, 그러한 문자열 $ B $는 항상 $ A $ 바로 뒤에 있다는 것입니다. 이 말이 이해가 안된다면 사전을 생각해봅시다. "abcd", "abcde"와 같은 단어가 있다고 가정합시다. 이를 사전순으로 배열하면 "abcd"까지 같으니 더 긴 문자열이 뒤로 오게 됩니다. 그렇게 뒤에 온 문자열은 항상 앞의 문자열을 접두사로 포함하고 있는 꼴이 될 것 입니다. 마지막으로..

문제 백준 16172번 풀이 번형된 문자열 $ S $를 입력 받고 0-9를 모두 제거합니다. 찾고자 하는 문자열 $ T $를 전처리한 문자열 $ S $에서 선형 탐색($ O(|S|) $)하여 찾아줍니다. 선형 탐색을 굳이 구현할 필요 없이 STL에서 stirng.find를 지원해주니 find의 반환값이 string::npos인지 확인만 해주면 됩니다. 다만 주의할 점은 $ S $에서 0-9를 제거할 때, $ S.erase $를 사용하면 최악의 경우 $ O(|S|^2) $으로 TLE가 날 수 있습니다. 이 때문에, 다른 변수를 만들어 전처리해야 합니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ul..