문자열 알고리즘(1)-애너그램 찾기, 팰린드롬 찾기

문자열 알고리즘

문자열 알고리즘은 기술 면접에 가장 자주 나오는 알고리즘입니다.

문자열 알고리즘에서 가장 많이 나오는 주제로는

• 애너그램 찾기
• 팰린드롬 찾기
• 마지막 숫자
• 시저의 암호

등이 있습니다.

 

이번 블로그에서는 애너그램 찾기와 팬린드롬 찾기 알고리즘에 대해 공부해보겠습니다.

애너그램 찾기

애너그램이란 숫서와 대소에 관계없이 똑같은 문자로 구성된 두 문자열을 의미합니다. 예를 들어 Car와 arc는 애너그램입니다. 

 

먼저 s1과 s2가 애너그램인지 아닌지를 판별해주는 함수를 작성해보겠습니다.

먼저 s1, s2를 인자로 받습니다. s1 ,s2 둘 다 띄어쓰기를 없애고 대문자를 소문자로 바꿉니다. 둘 다 정렬을 한 상태로 같은지 비교합니다. 두 인자가 같다면 True, 다르다면 False를 리턴합니다.

시간 복잡도

👉애너그램을 찾는 알고리즘은 sorted함수를 사용하므로 0(n log n)을 따릅니다.

 

팬린드롬 찾기

팬린드롬(회문)이란 앞에서 읽으나 거꾸로 읽으나 똑같은 단어를 뜻합니다. 예를 들어 mom, wow, Hannah 등이 모두 팰린드롬 입니다.

 

python 함수 - 문자열 슬라이싱

문자열 슬라이싱은 string[start:end:step]으로 나누어져 있습니다. start: 부분 문자열의 시작 인덱스입니다. 이 인덱스의 문자는 부분 문자열에 포함됩니다. 시작 인덱스를 생략하면 기본값인 0이 지정됩니다.  end: 부분 문자열의 끝 인덱스입니다. 이 인덱스의 문자는 부분 문자열에 포함되지 않습니다. end가 생략되거나 지정된 값이 문자열 길이를 초과하면 기존 문자열의 길이와 동일하다고 가정합니다.  step: 현재 문자에서 step간격으로 문자를 추출합니다. step을 생략하면 기본값인 1로 설정됩니다.

 

따라서 

를 출력하면

위의 결과가 출력됩니다.

 

이를 이용하여 문자열이 팰린드롬인지를 확인해보는 코드를 작성해보겠습니다.

 

먼저 s1이라는 문자열을 인자로 받습니다. s1에 존재하는 대문자들을 모두 소문자로 바꿉니다. 그리고 그 s1을 s1의 문자열을 뒤집은 s1과 비교하고 같으면 True, 다르면 False를 리턴합니다.

Hannah라는 단어가 팰린드롬인지 is_palindrome함수를 사용해서 확인해보면

 

True를 리턴하는 것을 알 수 있습니다.

 

시간 복잡도

👉리스트를 뒤집기 위해서는 요소 전체를 하나씩 비교하야 합니다. 따라서 전체 알고리즘의 시간 복잡도는 0(n)을 따릅니다.