[프로그래머스] 자동완성 (Python)

📌 자동완성

https://school.programmers.co.kr/learn/courses/30/lessons/17685

풀이과정

보통 이 문제를 트라이 자료구조를 이용해 푼다. 하지만 나는 그런 거 모르므로, 무작정 for문을 사용해서 풀기 시작했다. words 배열을 돌면서 각 단어마다 또 words 배열을 돌면서 같은 인덱스에 같은 값이 있는지, 그리고 그 전 인덱스에서도 모두 다 같은지 확인을 한다. 만약 값이 같다면, 다음 인덱스로 넘어가서 이 과정을 반복한다. 만약 단어 끝까지 돌았다면 그대로 값을 내고 그렇지 않다면 +1을 해서 정답을 도출한다.

def solution(words):
    answer = 0
    for word in words:
        r = False      
        for j in range(len(word)):
            i = 0
            for i in range(len(words)):
                if word == words[i]:
                    continue
                if len(words[i]) > j and word[j] == words[i][j] and word[:j] == words[i][:j]:
                    answer += 1
                    if j == len(word) - 1:
                        r = True
                    break
                    
                if i == len(words) - 1:
                    break
        if r!= True:
            answer += 1
    if len(words) == 1:
        return len(words[0])
    return answer

하지만 words 배열을 2중 for문으로 도는 것이 시간이 오래 걸려서 몇몇 테스트에서 시간초과가 발생하였다. 따라서 좀 더 효율적인 방법을 찾아보았다. sort를 쓰면, words 배열을 모두 돌지 않고 바로 앞단어와 뒷단어만 확인해주면 된다. 만약 단어별로 순서대로 결과값을 내야한다면 인덱스까지 넣어서 순서를 맞춰야하지만, 이 문제는 전체 문자 수를 다 더한 것이 답이므로, sort를 거리낌없이 사용해도 된다.

def solution(words):
  N = len(words)
  words.sort()
  result = [0] * N

  for i in range(N - 1):
      a = len(words[i])
      b = len(words[i + 1])
      for j in range(min(a, b)):
          if words[i][j] != words[i + 1][j]:
              j -= 1 
              break

      result[i] = max(result[i], min(a, j + 2))
      result[i + 1] = max(result[i + 1], min(b, j + 2))

  return sum(result)

✍ 끄적끄적

만약 시간이 넉넉하다면 파이썬의 startswith 함수를 이용하여 풀 수 있지 않을까?
단어마다 돌면서 startswith(word[:1]), startswith(word[:2]) 돌면서 있는 지 확인하면 될 것 같다.

def solution(words):
  N = len(words)
  result = 0
  for i in range(N):
      ans = 0
      for j in range(N):
          r = False
          for k in range(N):
              if i!= k and words[k].startswith(words[i][:j]):
                  r = True
                  ans = j
          if r == False:
              break
      result += min(ans+1, len(words[i])) 

  return result

궁금해서 한번 해봤다! 돌려보니 시간 초과 + TEST4 ERROR가 났다.

💯 정답

def solution(words):
  N = len(words)
  words.sort()
  result = [0] * N

  for i in range(N - 1):
      a = len(words[i])
      b = len(words[i + 1])
      for j in range(min(a, b)):
          if words[i][j] != words[i + 1][j]:
              j -= 1 
              break

      result[i] = max(result[i], min(a, j + 2))
      result[i + 1] = max(result[i + 1], min(b, j + 2))

  return sum(result)