문자열 (String)

#자료구조

문자열은 문자들의 집합, 배열로서 엄밀하게 자료 구조라고 볼 수 없지만 배열 (Array)과 유사하기 때문에 자료 구조의 하위 항목으로 묶었다.

문자열을 검색하기 위한 일반적인 자료 구조는 다음과 같이 있다.

그리고 문자열 관련 알고리즘은 다음과 같이 있다.

시간 복잡도

문자열은 배열과 유사하기 때문에 시간 복잡도 또한 같다.

Operation	Big-O	Note
부분 문자열 찾기	O(n.m)	This is the most naive case. There are more efficient algorithms for string searching such as the KMP algorithm
문자열 연결	O(n + m)
문자열 자르기	O(m)
문자열 분리	O(n + m)
양 끝 공백 제거	O(n)

문자열에서 특정 문자의 개수를 셀 때는 보통 hash table이나 map을 사용한다. 만약 언어에서 문자를 검색하는 함수를 내장하고 있다면 그것을 사용하자

아나그램은 원래의 모든 글자중 하나씩만 사용하여 새로운 단어나 구를 만드는 놀이이다.
두 문자열이 아나그램인지 확인하는 방법은 다음과 같이 있다.

두 문자열을 모두 정렬하고, 정렬 결과가 같은지 확인한다. O(n.log(n))의 시간 복잡도를 가진다.
각 문자를 소수에 대응 시키고, 그 숫자들을 모두 곱했을 때 아나그램은 같은 배수를 가져야 한다. (소인수 분해) O(n)의 시간 복잡도를 가진다.
각 문자가 등장한 개수를 확인한다. O(n)의 시간 복잡도를 가진다.

Palindrome은 앞으로 읽어도, 뒤로 읽어도 거꾸로해도 같은 문자열인 단어를 말한다.

문자열이 Palindrome인지 확인하는 방법은 다음과 같이 있다.