두 개의 문자열이 주어진다고 가정해 봅시다. 하나는 기준이 되는 문자열 str이고, 다른 하나는 패턴 문자열 patt입니다. 이때 우리가 해야 할 일은 str에서 가장 작은 인덱스에 등장하는 patt의 문자를 찾는 것입니다. 만약 patt의 어떤 문자도 str에 존재하지 않는다면 -1을 반환하면 됩니다.
예를 들어 입력이 str = "helloworld", patt = "wor"라고 해 보겠습니다. 이 경우 출력은 'o'가 됩니다. 'w'는 인덱스 6, 'o'는 인덱스 4, 'r'은 인덱스 7에 위치하므로, 세 문자 중 가장 앞쪽에 있는 'o'가 정답이기 때문입니다.
해결 접근 방법
이 문제는 이중 반복문을 사용해 다음과 같은 단계로 해결할 수 있습니다.
- i를 0부터 patt의 길이까지 반복합니다.
- j를 0부터 Str의 길이까지 반복합니다.
- patt[i]와 Str[j]가 같고, j가 현재 minimum_index보다 작다면
- minimum_index를 j로 갱신합니다.
- 내부 반복문을 빠져나옵니다. (더 앞쪽 인덱스는 존재하지 않으므로)
- patt[i]와 Str[j]가 같고, j가 현재 minimum_index보다 작다면
- j를 0부터 Str의 길이까지 반복합니다.
- 반복이 끝난 후 minimum_index가 초기값(10^9)과 다르다면 Str[minimum_index]를 반환합니다.
- 그렇지 않다면 일치하는 문자가 없다는 의미이므로 -1을 반환합니다.
여기서 minimum_index의 초기값을 매우 큰 수(10^9)로 설정하는 이유는, 아직 어떤 문자도 발견되지 않았음을 표시하기 위함입니다.
구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
def get_min_index_char(Str, patt):
minimum_index = 10**9
for i in range(len(patt)):
for j in range(len(Str)):
if (patt[i] == Str[j] and j < minimum_index):
minimum_index = j
break
if (minimum_index != 10**9):
return Str[minimum_index]
else:
return -1
Str = "helloworld"
patt = "wor"
print(get_min_index_char(Str, patt))입력
"helloworld", "wor"
출력
o
시간 복잡도 분석
위 방법의 시간 복잡도는 O(n × m)입니다. 여기서 n은 Str의 길이, m은 patt의 길이입니다. 모든 패턴 문자에 대해 전체 문자열을 탐색하기 때문입니다.
만약 더 효율적인 방법이 필요하다면, 각 패턴 문자에 대해 Str.find() 메서드를 활용해 한 번의 순회로 해결할 수 있습니다.
def get_min_index_char_v2(Str, patt):
result_index = len(Str)
for ch in patt:
idx = Str.find(ch)
if idx != -1 and idx < result_index:
result_index = idx
return Str[result_index] if result_index < len(Str) else -1이 버전 역시 최악의 경우 O(n × m)이지만, 내부적으로 최적화된 C 구현을 사용하므로 실제 실행 속도는 훨씬 빠릅니다.