[Python] 백준 2179 비슷한 단어

1. 문제 - 백준 2179 비슷한 단어

https://www.acmicpc.net/problem/2179

 

💡알고리즘 - 해시

딕셔너리를 활용해 모든 입력 단어의 접두사 별 갯수를 구하는 점에서 해시를 이용하는 문제이다.

 

❌ 시간초과 풀이

n = int(input())
arr = []
for _ in range(n):
  arr.append(input())

_len = 0
answer = []

for i in range(n-1):
  for j in range(i+1, n):
    cnt = 0
    if len(arr[i]) < len(arr[j]):
      m = len(arr[i])
    else:
      m = len(arr[j])
    for k in range(m):      # arr[i]와 arr[j] 문자열의 겹치는 접두사의 길이를 구한다.
      if arr[i][k] == arr[j][k]:
        cnt += 1

    if _len <= cnt:       # 접두사 길이의 최대값 갱신
      _len = cnt
      answer.append([arr[i], arr[j], i, j, cnt])   # 이후 문제 조건에 맞게 정렬하기 위해서 추가

answer.sort(key=lambda x:(-x[4], x[2], x[3]))     # 접두사의 길이 내림차순, 입력받은 순서 오름차순으로 정렬
print(answer[0][0])
print(answer[0][1])

- 정직하게 입력받은 문자열끼리 하나하나 겹치는 접두사를 비교했다.

- N이 20,000 이기 때문에 3중 반복문으로 알고리즘을 짜게되면 시간초과가 발생한다.

- 따라서 이를 최대 O(N^2) 이내로 풀 수 있는 방법을 고민해봐야한다.

 

❌ 틀린 풀이 (딕셔너리 활용)

 

다른 사람들의 풀이를 살펴보니 각 단어에서 나올 수 있는 모든 접두사의 등장 빈도를 딕셔너리를 통해 저장하여 문제를 풀었다.

이 아이디어를 참고해서 다음과 같이 풀이했다.

from collections import defaultdict

dic = defaultdict(int)
n = int(input())
arr = []      # 문자열들을 저장할 배열
for _ in range(n):
  word = input()
  arr.append(word)
  for i in range(len(word)):    # 입력받는 문자 별로, 해당 문자에서 나올 수 있는 모든 접두사에 대한 갯수를 카운팅한다.
    dic[word[:i]] += 1

answer = []
maxlen, maxprefix = 0, ""       # 가장 빈번하게 겹치는 접두사의 최대길이, 접두사
# 비슷한 문자를 찾으려면 접두사의 빈도수가 적어도 2 이상이어야한다.
  if v >= 2 and maxlen <= len(k):
    maxlen = len(k)
    maxprefix = k
    
for i, w in enumerate(arr):
  if maxprefix == w[:maxlen]:     # 가장 빈번하게 겹치는 최대 길이의 접두사와 겹치는 단어가 있으면 추가한다.
    answer.append((w, i))
answer.sort(key=lambda x:x[1])   # 입력 순서대로 정렬함 (먼저 입력한 순서대로 출력해야 하므로)

print(answer[0][0])
print(answer[1][0])

 

하지만 이 풀이도 34% 부근에서 틀렸다고 나온다.

2가지를 수정해야한다.

 

1) for i in range(len(word)):

파이썬에서는 루프가 len(word)-1 까지 도므로, 이렇게 되면 그 문자열 자체가 접두사인 경우를 포함할 수 없다.

따라서 이부분을 for i in range(len(word)+1) 로 하여 그 문자열 자체도 접두사로서 포함하여 갯수를 세도록 한다.

 

2) if v >= 2 and maxlen <= len(k):

maxlen <= len(k)를 하게 되면 최대값을 제대로 갱신하지 못한다. 이부분을 maxlen < len(k)로 수정한다.

 

✅ 수정한 최종 통과 풀이 (딕셔너리 활용)

from collections import defaultdict

dic = defaultdict(int)
n = int(input())
arr = []
for _ in range(n):
  word = input()
  arr.append(word)
  for i in range(len(word)+1):    # 수정한 부분 1
    dic[word[:i]] += 1

answer = []
maxlen, maxprefix = 0, ""
for k, v in dic.items():
  if v >= 2 and maxlen < len(k):   # 수정한 부분 2
    maxlen = len(k)
    maxprefix = k
    
for i, w in enumerate(arr):
  if maxprefix == w[:maxlen]:
    answer.append(w)               # 수정한 부분 3: 입력한 순서대로 2개의 단어를 출력하면 되니까 이후에 굳이 정렬할 필요가 없음.

print(answer[0])
print(answer[1])