정규식
-
알고리즘 문제풀때 정규식(Regex)을 쓰는것이 좋을까??알고리즘/알고리즘 Tip! 2020. 4. 20. 23:10
정규 표현식은 특정한 규칙을 가진 문자열의 집합을 표현하기 위해 쓰이는 형식 언어입니다. 하지만, 알고리즘 성능에는 그다지 좋지가 않습니다. 그 이유는 "백트래킹" 때문입니다. 정규식은 왼쪽에서 오른쪽으로 탐색을 하는데 100% 매칭 되지 않으면 다시 뒤로 되돌아가면서 매칭을 시도합니다. 이를 백트래킹이라고 합니다. 자바 같은 경우에는 심지어 컴파일 작업을 거쳐야지만 사용이 가능합니다. Pattern.compile("ABC").matcher(s).find() s.contains("ABC") 다음 두 코드 중 어느 게 더 빠를까요?? 전자는 컴파일하고 (상대적으로) 복잡한 정규 표현식을 반복하므로 단순히 일련의 문자를 찾는 후자가 조금 더 빠릅니다. 그러면 정규식을 안 쓰는 게 좋지 않는가?? 속도만을 생..