문제 소개
서로 다른 문자들로만 구성된 문자열 s와 문자열 배열 words가 주어졌다고 가정해 봅시다. 어떤 문자열의 모든 문자가 문자열 s 안에 포함되어 있다면, 그 문자열을 '일관된(consistent) 문자열'이라고 정의합니다. 우리의 목표는 words 배열에 있는 문자열 중에서 일관된 문자열이 총 몇 개인지 찾는 것입니다.
예를 들어, 입력이 다음과 같다면:
- s = "px"
- words = ["ad", "xp", "pppx", "xpp", "apxpa"]
출력은 3이 됩니다. 'p'와 'x'라는 두 문자만으로 이루어진 문자열이 ["xp", "pppx", "xpp"]로 세 개 존재하기 때문입니다. 반면 "ad"는 'a', 'd'가 s에 없고, "apxpa"는 'a'가 포함되어 있어 제외됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 변수 count를 0으로 초기화합니다.
- words 배열의 각 문자열을 순서대로 확인합니다.
- 각 문자열의 모든 문자가 s에 포함되어 있는지 검사합니다.
- 검사 중 하나라도 s에 없는 문자가 발견되면 즉시 해당 문자열 검사를 중단하고 다음 문자열로 넘어갑니다.
- 모든 문자가 통과한 경우에만 count를 1 증가시킵니다.
- 모든 문자열 검사가 끝나면 count를 반환합니다.
파이썬 구현 코드
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
def solve(s, words):
count = 0
for i in range(len(words)):
for j in range(len(words[i])):
if words[i][j] not in s:
break
else:
count += 1
return count
s = "px"
words = ["ad", "xp", "pppx", "xpp", "apxpa"]
print(solve(s, words))여기서 눈여겨볼 부분은 파이썬의 for-else 문법입니다. 내부 for 루프가 break 없이 정상적으로 모두 실행되면 else 블록이 실행됩니다. 즉, 문자열의 모든 문자가 s에 포함되어 있을 때만 else 블록의 count += 1이 수행되므로, 별도의 플래그 변수 없이 깔끔하게 로직을 표현할 수 있습니다.
입력 및 출력 결과
입력:
"px", ["ad", "xp", "pppx", "xpp", "apxpa"]
출력:
3
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N × M)입니다. 여기서 N은 words 배열의 문자열 개수, M은 각 문자열의 평균 길이입니다. 최악의 경우 모든 문자열의 모든 문자를 한 번씩 확인해야 하기 때문입니다. 만약 s를 집합(set)으로 변환하여 멤버십 검사를 하면, 문자 포함 여부 확인이 O(1)로 빨라져 전체 성능을 더욱 향상시킬 수 있습니다.