문제 설명
서로 다른 단어로 이루어진 리스트가 주어졌을 때, 리스트에서 두 개의 서로 다른 단어를 골라 이어 붙였을 때 회문(palindrome), 즉 앞에서 읽으나 뒤에서 읽으나 같은 문자열이 되는 조합이 총 몇 가지인지 구하는 프로그램을 작성해 보겠습니다.
예를 들어 입력이 words = ["time", "emit", "mo", "m"]라고 한다면, 출력은 3이 됩니다. "timeemit", "emittime", "mom"의 세 가지 회문을 만들 수 있기 때문입니다.
풀이 접근 방식
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- ln은 배열에 들어 있는 단어의 개수입니다.
- k를 0부터 1까지, 즉 총 두 번 반복합니다.
- 각 반복 안에서 i를 0부터 ln − 1까지 순회합니다.
- 그다음 j를 i + 1부터 ln − 1까지 순회하며, words[i]와 words[j]를 이어 붙인 문자열이 회문이면 res에 1을 더하고, 아니면 0을 더합니다.
- 한 번의 전체 순회가 끝나면 words 리스트를 뒤집습니다. 이렇게 하면 (i, j) 순서와 (j, i) 순서의 조합을 모두 검사할 수 있습니다.
모든 반복이 끝나면 res를 반환합니다.
예제 코드
class Solution: def solve(self, words): def is_palindrome(w1, w2): w3 = w1 + w2 return w3 == w3[::-1] res = 0 ln = len(words) for k in range(2): for i in range(ln): for j in range(i + 1, ln): res += is_palindrome(words[i], words[j]) words = words[::-1] return res ob = Solution() words = ["time", "emit", "mo", "m"] print(ob.solve(words))
입력
["time", "emit", "mo", "m"]
출력
3
동작 원리 살펴보기
내부 함수 is_palindrome은 두 단어를 이어 붙인 문자열 w3가 자신을 뒤집은 문자열과 같은지 비교하여 회문 여부를 판별합니다. 파이썬의 슬라이싱 문법인 w3[::-1]을 사용하면 문자열을 손쉽게 뒤집을 수 있습니다.
바깥쪽 반복문을 두 번 실행하는 이유는 단어의 순서 때문입니다. 예를 들어 "time" + "emit"과 "emit" + "time"은 서로 다른 결과를 낼 수 있으므로, 첫 번째 순회에서는 정방향 조합을, 리스트를 뒤집은 후 두 번째 순회에서는 역방향 조합을 검사하게 됩니다.
시간 복잡도는 단어 쌍을 모두 검사해야 하므로 O(n² × L)입니다. 여기서 n은 단어의 개수, L은 평균 단어 길이입니다. 단어 수가 많아지면 해시 맵을 활용한 최적화도 가능하지만, 직관적인 이해에는 위의 브루트포스 방식이 가장 적합합니다.