[baekjoon] 백준 14426번(파이썬): 접두사 찾기

문제

14426번: 접두사 찾기

알고리즘

- 정렬을 통해 절대로 접두사가 될 수 없는 문자열을 제외하여 리스트를 새로 만든다.

- 반복문을 통해 집합 s와 접두사가 될 수 있는 문자열을 비교한다.

- 비교하는 과정에서도 접두사가 될 수 없는 문자열이 나올 경우 break를 통해 다음 문자열을 비교한다.

코드

import sys


n, m = map(int, sys.stdin.readline().split())

s = [str(sys.stdin.readline().rstrip("\n")) for _ in range(n)]
targets = [str(sys.stdin.readline().rstrip("\n")) for _ in range(m)]

# 집합 s와 m개의 문자열을 비교하기 위해 오름차순 정렬
s.sort()
targets.sort()
words = [] # 접두사가 될 수 있는 문자열 리스트

# 반복문을 통해 집합 s의 제일 큰 문자열의 앞 문자와 target 문자열의 앞 문자를 비교
for i in range(m):
    # target 문자열의 앞 문자가 더 크면 그 다음 target 문자열은 집합 s의 접두사가 될 수 없다.
    if s[-1][0] < targets[i][0]:
        break
    # 집합 s의 제일 큰 문자열의 앞 문자가 더 크면 접두사가 될 수 있으므로 words에 추가
    words.append(targets[i])

cnt = 0 # 접두사 개수

# 반복문을 통해 words의 문자열이 집합 s의 접두사인지 확인
for i in words:
    for j in s:
        # words의 문자열의 앞 문자가 집합 s의 문자열의 앞문자보다 작으면
        # 그 다음 집합 s의 문자열의 접두사가 될 수 없으므로 반복문을 멈춘다.
        if i[0] < j[0]:
            break

        # 집합 s의 문자열을 words의 문자열의 길이만큼 잘랐을 때 words의 문자열과 같다면
        # words의 문자열이 집합 s의 문자열의 접두사가 된다.
        if j[:len(i)] == i:
            cnt += 1
            break

print(cnt)

 

실패한 코드(시간 초과)

import sys


n, m = map(int, sys.stdin.readline().split())

words = [str(sys.stdin.readline().rstrip("\n")) for _ in range(n)]
targets = [str(sys.stdin.readline().rstrip("\n")) for _ in range(m)]
words.sort()
targets.sort()

cnt = 0
for i in targets:
    for j in words:
        if i[0] < j[0]:
            break

        if j[:len(i)] == i:
            cnt += 1
            break

print(cnt)

이중 for문만으로는 무조건 시간 초과가 난다고 생각하여 for문 중에 시간을 줄이려고 했지만 역시나 시간 초과가 났다. 어떻게 하면 시간을 줄이지 다시 생각을 하던 중 절대로 접두사가 될 수 없는 문자열을 제외하면 되지 않을까?라는 생각을 하여 절대로 접두사가 될 수 없는 문자열을 제외하고 새로운 리스트를 만들어 집합 s와 비교하는 알고리즘으로 문제를 해결했다. 

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법