문제 개요
소문자 알파벳으로만 구성된 두 개의 문자열이 주어집니다. 이때 아래 조건을 모두 만족하는 인덱스 사중조(p, q, r, s)의 개수를 구해야 합니다.
0 ≤ p ≤ q ≤ 첫 번째 문자열의 길이
0 ≤ r ≤ s ≤ 두 번째 문자열의 길이
첫 번째 문자열에서 인덱스 p로 시작해 q에서 끝나는 부분 문자열과, 두 번째 문자열에서 인덱스 r로 시작해 s에서 끝나는 부분 문자열이 서로 동일해야 합니다.
위 조건을 만족하는 모든 사중조 중에서 q − r의 값이 가능한 한 최소여야 합니다.
핵심은 각 문자에 대해 첫 번째 문자열에서는 가장 앞선 위치를, 두 번째 문자열에서는 가장 뒤쪽 위치를 선택해야 q − r을 최소화할 수 있다는 점입니다.
예시
예를 들어 firstString = 'hgfn', secondString = 'gfrt'가 입력으로 주어지면 출력은 2가 됩니다.
'g'와 'f'가 두 문자열에 공통으로 등장하며, (1, 1, 0, 0)과 (2, 2, 1, 1)이라는 두 개의 사중조가 조건을 만족하면서 q − r의 최솟값을 가지기 때문입니다.
해결 접근 방법
이 문제는 각 알파벳이 두 문자열에서 등장하는 위치를 활용하면 효율적으로 풀 수 있습니다. 단계별로 살펴보겠습니다.
- ord() 함수를 정의합니다. 이 함수는 문자 ch를 받아 해당 문자의 유니코드 값을 반환합니다.
- left := 크기 26의 리스트, 무한대(infinity)로 초기화 — 첫 번째 문자열에서 각 문자가 처음 등장하는 가장 작은 인덱스를 저장합니다.
- right := 크기 26의 리스트, -1로 초기화 — 두 번째 문자열에서 각 문자가 마지막으로 등장하는 가장 큰 인덱스를 저장합니다.
- res := 0 (결과 카운터), mi := 무한대 (최소 차이 값)
- 첫 번째 문자열의 각 인덱스 i와 문자 ch에 대해 left[ord(ch) - ord('a')]를 현재 값과 i 중 더 작은 값으로 갱신합니다.
- 두 번째 문자열의 각 인덱스 i와 문자 ch에 대해 right[ord(ch) - ord('a')]를 현재 값과 i 중 더 큰 값으로 갱신합니다.
- i를 0부터 25까지 순회하면서 left[i]가 유효한 값이라면 mi를 min(mi, left[i] - right[i])로 갱신합니다.
- 다시 i를 0부터 25까지 순회하면서 left[i]와 right[i]가 모두 유효하고 left[i] - right[i]가 mi와 같으면 res를 1 증가시킵니다.
- 최종적으로 res를 반환합니다.
구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(firstString, secondString):
left = [float('inf')] * 26
right = [-1] * 26
res = 0
mi = float('inf')
for i, ch in enumerate(firstString):
left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
for i, ch in enumerate(secondString):
right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
for i in range(26):
if left[i] != -1:
mi = min(mi, left[i] - right[i])
for i in range(26):
if left[i] != float('inf') and right[i] != -1:
if left[i] - right[i] == mi:
res += 1
return res
print(solve('hgfn', 'gfrt'))
입력
'hgfn', 'gfrt'
출력
2
복잡도 분석
시간 복잡도: O(n + m)입니다. n과 m은 각각 두 문자열의 길이이며, 각 문자열을 한 번씩 순회한 뒤 크기가 26으로 고정된 배열을 두 번만 더 확인하기 때문입니다.
공간 복잡도: O(1)입니다. 알파벳 소문자 개수(26)에 해당하는 고정 크기의 배열 두 개만 추가로 사용합니다.