14426번 접두사 찾기

14426번 접두사 찾기 (Prefix Search)

문제

N개의 문자열로 이루어진 집합 S가 주어집니다.

M개의 문자열이 주어질 때, 각 문자열이 집합 S의 어떤 문자열의 접두사인지 판단하여,

그러한 문자열의 개수를 출력해야 합니다.

예시

입력

5 10
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
star
start
code
sunday
coding
cod
online
judge
plus

출력

7

설명

아래는 M개의 문자열 중 접두사에 해당하는 것들입니다:

검사 문자열	접두사 대상 문자열 (S 내)	접두사 여부
baekjoon	baekjoononlinejudge	O
star	startlink	O
start	startlink	O
code	codeplus	O
sunday	sundaycoding	O
coding	codingsh	O
cod	codeplus, codingsh	O
online		X
judge		X
plus		X

총 7개가 접두사 조건을 만족합니다.

아이디어

---

정렬된 배열(arr1)

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}

인덱스

0: baekjoononlinejudge

1: codeplus

2: codingsh

3: startlink

4: sundaycoding

검사할 배열(arr2)

{baekjoon, star, start, code, sunday, coding, cod, online, judge, plus}

① 검사 문자열: "baekjoon"

현재 탐색범위

• left = 0
• right = 4
• mid = (left + right) // 2 → 2
• arr2[i] = "baekjoon"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  현재 중앙 인덱스는 2이며 "codingsh"를 가리킵니다.

  "baekjoon"이 "codingsh"의 접두사인지 확인했지만 False입니다.

  사전순 비교 시 'b' < 'c'이므로 "baekjoon"은 "codingsh"보다 앞에 있습니다.

  즉 "baekjoon"이 존재한다면 왼쪽 구간에 있습니다.

  탐색 범위를 왼쪽으로 좁히기 위해 right = mid - 1 = 1로 업데이트합니다.

현재 탐색범위

• left = 0
• right = 1
• mid = (left + right) // 2 → 0
• arr2[i] = "baekjoon"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
 ↑ (mid=0)

설명

  중앙 인덱스 0은 "baekjoononlinejudge"입니다.

  이 문자열은 "baekjoon"으로 시작합니다.

  조건을 만족했으므로 탐색을 종료합니다.

② 검사 문자열: "star"

현재 탐색범위

• left = 0
• right = 4
• mid = (left + right) // 2 → 2
• arr2[i] = "star"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "star"로 시작하지 않습니다.

  사전순으로 'c' < 's'이므로 "star"가 더 뒤에 있습니다.

  탐색 범위를 오른쪽으로 좁히기 위해 left = mid + 1 = 3으로 업데이트합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = (left + right) // 2 → 3
• arr2[i] = "star"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "star"로 시작합니다.

  조건을 만족하므로 탐색을 종료합니다.

③ 검사 문자열: "start"

현재 탐색범위

• left = 0
• right = 4
• mid = (left + right) // 2 → 2
• arr2[i] = "start"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "start"로 시작하지 않습니다.

  'c' < 's'이므로 "start"가 오른쪽에 있을 가능성이 있습니다.

  따라서 left = mid + 1 = 3으로 이동합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = 3
• arr2[i] = "start"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "start"로 시작합니다.

  탐색을 종료합니다.

④ 검사 문자열: "code"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "code"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "code"로 시작하지 않습니다.

  두 문자열을 비교하면 "codingsh"의 세 번째 글자는 'd', "code"의 세 번째 글자도 'd'이지만, 네 번째에서 "codingsh"는 'i', "code"는 'e'입니다.

  'i' > 'e'이므로 "codingsh"가 "code"보다 뒤에 있습니다.

  따라서 "code"가 존재한다면 왼쪽에 있어야 하므로 right = mid - 1 = 1로 이동합니다.

현재 탐색범위

• left = 0
• right = 1
• mid = 0
• arr2[i] = "code"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
 ↑ (mid=0)

설명

  "baekjoononlinejudge"는 "code"로 시작하지 않으며 'b' < 'c'입니다.

  따라서 "code"는 오른쪽에 있을 수 있으므로 left = mid + 1 = 1로 이동합니다.

현재 탐색범위

• left = 1
• right = 1
• mid = 1
• arr2[i] = "code"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
           ↑ (mid=1)

설명

  "codeplus"는 "code"로 시작합니다.

  탐색 종료.

⑤ 검사 문자열: "sunday"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "sunday"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "sunday"로 시작하지 않으며 'c' < 's'입니다.

  따라서 "sunday"는 오른쪽에 있을 가능성이 높습니다.

  left = mid + 1 = 3으로 이동합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = 3
• arr2[i] = "sunday"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "sunday"로 시작하지 않습니다.

  's' = 's'이지만 두 번째 글자 't' < 'u'이므로 "sunday"는 "startlink"보다 뒤쪽입니다.

  따라서 left = mid + 1 = 4로 이동합니다.

현재 탐색범위

• left = 4
• right = 4
• mid = 4
• arr2[i] = "sunday"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                                  ↑ (mid=4)

설명

  "sundaycoding"은 "sunday"로 시작합니다.

  탐색 종료.

⑥ 검사 문자열: "coding"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "coding"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "coding"으로 시작합니다.

  탐색 종료.

⑦ 검사 문자열: "cod"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "cod"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "cod"로 시작합니다.

  탐색 종료.

⑧ 검사 문자열: "online"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "online"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "online"으로 시작하지 않으며 'c' < 'o'입니다.

  따라서 "online"은 오른쪽에 있을 가능성이 있어 left = mid + 1 = 3으로 이동합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = 3
• arr2[i] = "online"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "online"으로 시작하지 않으며 's' > 'o'입니다.

  따라서 "online"은 왼쪽에 있을 가능성이 있어 right = mid - 1 = 2로 이동합니다.

현재 탐색범위

• left = 3
• right = 2

  탐색 종료 (존재하지 않음).

⑨ 검사 문자열: "judge"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "judge"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "judge"로 시작하지 않으며 'c' < 'j'입니다.

  따라서 "judge"는 오른쪽에 있을 가능성이 있어 left = mid + 1 = 3으로 이동합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = 3
• arr2[i] = "judge"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "judge"로 시작하지 않으며 's' > 'j'입니다.

  따라서 "judge"는 왼쪽에 있을 가능성이 있어 right = mid - 1 = 2로 이동합니다.

탐색 종료 (존재하지 않음).

⑩ 검사 문자열: "plus"

현재 탐색범위

• left = 0
• right = 4
• mid = 2
• arr2[i] = "plus"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                ↑ (mid=2)

설명

  "codingsh"는 "plus"로 시작하지 않으며 'c' < 'p'입니다.

  따라서 "plus"는 오른쪽에 있을 가능성이 있어 left = mid + 1 = 3으로 이동합니다.

현재 탐색범위

• left = 3
• right = 4
• mid = 3
• arr2[i] = "plus"이고

{baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding}
                                           ↑ (mid=3)

설명

  "startlink"는 "plus"로 시작하지 않으며 's' > 'p'입니다.

  따라서 "plus"는 "startlink"보다 앞에 있어야 하므로 right = mid - 1 = 2로 이동합니다.

탐색 종료 (존재하지 않음).

✅ 최종 결과:

접두사 조건을 만족하는 검사 문자열:

baekjoon, star, start, code, sunday, coding, cod → 총 7개.

전체코드

N,M=map(int,input().split())
arr1=[input() for _ in range(N)]
arr2=[input() for _ in range(M)]
check=[0 for _ in range(M)]
cnt=0
arr1.sort()
for i in range(M):
    k=arr2[i]
    left=0
    right=N-1
    while left<=right:
        mid=(left+right)//2
        if k in arr1[mid][:len(k)+1]:
            check[i]=1
            break
        if arr1[mid]

결론

조건	사용 이유
arr1.sort()	이진 탐색을 위한 정렬
이진 탐색	시간 효율성 확보 (O(M log N))

입력 조건이 크고, 문자열 길이도 길 수 있기 때문에 단순 탐색이 아닌 정렬 후 이진 탐색이 핵심입니다.

---