leetcode hard : Guess the Word

링크 : Guess the Word - LeetCode

풀기 전

• 인풋 분포에 따라서 아무리 좋은 알고리즘이어도 실패할 수 있을거같다.
• 요구사항을 만족시킬 수 있다는 보장이 100% 되어있지 않으니 최대한 후보 수를 줄여나가는게 최선이다.
• 특정 단어가 주어졌을 때 결과값으로 나온 숫자를 보고 후보를 쳐낼 수 있다.

코드 설명

class Solution:
    def findSecretWord(self, words: List[str], master: 'Master') -> None:
        countMatch = lambda w1, w2 : sum(1 for i in range(6) if w1[i] == w2[i])
        for i in range(30):
            word = words[random.randint(0, len(words)-1)]
            matched = master.guess(word)
            if matched == 6: return
            words = [c for c in words if countMatch(c, word) == matched]

• countMatch 함수 : 두 단어를 받아 매칭되는 문자 수 반환
• word : guess에 넣어볼 단어. 랜덤하게 결정
• loop 과정
  • master.guess를 호출한다.
  • 같은 매칭수가 걸리는 후보만 남긴다.
  • 다음 word를 선정한다.

복잡도 분석

루프는 최악의 경우라도 30회 이하로 고정된 횟수만 호출된다.

따라서 루프 횟수는 시간복잡도 분석과는 무관

후보 추리는 과정에서 리스트를 한번 훑으므로 O(n)