Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 푸는 최단 완성 단어(Shortest Completing Word) 문제

문제 개요

단어 목록(words)과 번호판 문자열(licensePlate)이 주어졌을 때, 번호판에 포함된 모든 문자를 담고 있는 단어 중 가장 짧은 단어를 찾는 것이 목표입니다. 이처럼 조건을 만족하는 단어를 '완성 단어(completing word)'라고 부릅니다.

이 문제에는 몇 가지 규칙이 있습니다.

  • 대소문자는 구분하지 않습니다.
  • 정답이 반드시 존재한다고 보장됩니다.
  • 조건을 만족하는 단어가 여러 개라면, 배열에서 먼저 등장하는 단어를 반환합니다.
  • 번호판에는 같은 문자가 여러 번 나타날 수 있으므로, 필요한 개수만큼 해당 문자를 단어가 포함해야 합니다.

예를 들어 번호판이 "PP"라면, 단어 "pile"은 P가 하나뿐이라 조건을 충족하지 못하지만, "topper"는 P가 두 개 있으므로 완성 단어가 될 수 있습니다.

입력 및 출력 예시

licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]가 주어진 경우를 살펴보겠습니다.

번호판에서 필요한 문자는 S, P, S, T입니다. 이 네 글자를 모두 포함하는 단어 중 가장 짧은 것은 "steps"이므로 출력은 "steps"가 됩니다.

풀이 접근 방법

다음 단계를 따라 문제를 해결할 수 있습니다.

  1. 알파벳 소문자 전체("abcdefghijklmnopqrstuvwxyz")를 기준 문자열로 정의합니다.
  2. licensePlate에서 알파벳에 해당하는 문자만 골라 소문자로 변환한 리스트(letters)를 만듭니다. 숫자나 공백은 자동으로 제외됩니다.
  3. 조건을 만족하는 단어를 담을 빈 리스트(valid_words)를 준비합니다.
  4. words의 각 단어 i에 대해 다음을 검사합니다.
    • letters의 각 문자 j에 대해, letters 안에서 j의 개수가 단어 i 안에서 j의 개수보다 작거나 같은지 확인합니다.
    • 모든 문자에 대해 조건이 성립하면 해당 단어를 valid_words에 추가합니다.
  5. 마지막으로 valid_words에서 길이가 가장 짧은 단어를 반환합니다.

파이썬 코드 구현

class Solution:
    def shortestCompletingWord(self, licensePlate, words):
        alphabet = "abcdefghijklmnopqrstuvwxyz"
        letters = [s.lower() for s in licensePlate if s.lower() in alphabet]
        valid_words = []
        for i in words:
            append = True
            for j in letters:
                append = append and (letters.count(j) <= i.count(j))
            if append:
                valid_words.append(i)
        return min(valid_words, key=len)

ob = Solution()
print(ob.shortestCompletingWord("1s3 PSt", ["step", "steps", "stripe", "stepple"]))

실행 결과

입력: "1s3 PSt", ["step", "steps", "stripe", "stepple"]

출력:

steps

코드 설명

리스트 컴프리헨션을 사용해 licensePlate에서 숫자와 공백을 걸러내고 알파벳만 소문자로 추출합니다. 이후 각 단어가 필요한 문자를 충분히 포함하는지 count() 메서드로 검사하고, 조건을 통과한 단어들 중 min() 함수에 key=len 옵션을 적용해 가장 짧은 단어를 선택합니다.

성능 개선 팁: Counter 활용

위 코드는 letters.count(j)를 반복 호출하므로 단어가 길어질수록 비효율적일 수 있습니다. collections.Counter를 사용하면 문자 빈도를 한 번만 계산해 더 깔끔하고 빠르게 처리할 수 있습니다.

from collections import Counter

class Solution:
    def shortestCompletingWord(self, licensePlate, words):
        need = Counter(c.lower() for c in licensePlate if c.isalpha())
        best = None
        for w in words:
            wc = Counter(w.lower())
            if not (need - wc):  # 필요한 문자를 모두 충족하는 경우
                if best is None or len(w) < len(best):
                    best = w
        return best

Counter의 뺄셈 연산(need - wc) 결과가 비어 있다면, 해당 단어가 번호판에 필요한 모든 문자를 요구 개수만큼 포함한다는 의미입니다. 이 방식은 코드도 간결해지고 실행 속도 면에서도 유리합니다.