Python에서 주어진 단어들을 조합해 두 글자 문자열을 만들 수 있는지 확인하는 방법

문제 이해하기

길이가 2인 문자열 s와, 모든 단어의 길이가 2인 단어 목록 w가 주어졌다고 가정해 봅시다. 이때 w에 있는 단어들을 서로 이어 붙여서 만든 문자열 안에 s가 부분 문자열로 포함될 수 있는지 확인해야 합니다.

예를 들어, 입력이 s = "no", w = ["ol", "on", "ni", "to"]라면 출력은 True입니다. 단어들을 "onol"처럼 이어 붙이면 그 안에 "no"가 포함되기 때문입니다.

해결 접근 방식

이 문제는 다음 단계를 통해 해결할 수 있습니다.

• n := w에 있는 단어의 개수
• char_0 := False, char_1 := False로 초기화
• i를 0부터 n-1까지 반복:
  • w[i]가 s와 같으면 True 반환
  • s[0]이 w[i]의 두 번째 문자(w[i][1])와 같으면 char_0 := True
  • s[1]이 w[i]의 첫 번째 문자(w[i][0])와 같으면 char_1 := True
  • char_0과 char_1이 모두 True이면 True 반환
• 반복이 끝나면 False 반환

동작 원리

핵심 아이디어는 두 가지 경우를 구분하는 것입니다. 첫째, 어떤 단어 하나가 s와 정확히 일치하면 바로 성공입니다. 둘째, 한 단어의 끝 문자가 s의 첫 문자와 일치하고(연결 지점의 앞부분), 다른 단어의 시작 문자가 s의 두 번째 문자와 일치하면(연결 지점의 뒷부분), 두 단어를 적절히 이어 붙였을 때 s가 가운데에 걸쳐 나타날 수 있습니다. 두 조건이 모두 충족되면 True를 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해할 수 있습니다.

def solve(s, w):
    n = len(w)
    char_0 = False
    char_1 = False
    for i in range(n):
        if w[i] == s:
            return True
        if s[0] == w[i][1]:
            char_0 = True
        if s[1] == w[i][0]:
            char_1 = True
        if char_0 and char_1:
            return True
    return False

s = "no"
w = ["ol", "on", "ni", "to"]
print(solve(s, w))

입력

"no", ["ol", "on", "ni", "to"]

출력

True

복잡도 분석

이 알고리즘은 단어 목록을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리는 상수 개수의 불린 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 단어 목록이 매우 커져도 효율적으로 동작합니다.