[boj1148] word A의 알파벳으로 word B를 만들 수 있니? Counter로 비교하기

boj 1148 백준 1148 단어 만들기

두 단어 간의 포함 관계

word1의 알파벳들로 word2를 만들 수 있을까? 알파벳이 각각 몇개씩 포함되어 있는지 counter를 만든 후에, word2의 알파벳 각각이 word1에 모두 포함되어 있으면 가능하다.

word1에 a가 1개 이상 있어야 하고, b는 word1에 1개 이상, c도 word1에 1개 이상 들어 있으면 된다. word2의 char를 loop돌면서 word1의 counter와 비교해주면 되는 것이다. 코드는 아래 문제 솔루션 1번 부분에 담겨 있다.

Question

결국엔 퍼즐 9개 알파벳과 사전이 주어질 때, 알파벳을 조합해서 사전 속 단어를 몇 개나 만들 수 있는지?
가운데 문자는 꼭 활용해야 하는데, 가운데 어떤 알파벳이 들어가야 최대치가 되고 최소치가 되는지? 뽑아내는 것

사전에는 단어 최대 20만 개.. 사전 속 단어들을 정렬 같은 거 하면 안된다.

Solution

1. 사전에서 puzzle로 만들 수 있는 단어들을 추출 (counter 활용)
2. puzzle 문자를 하나씩 가운데에 놨을 때 가능한 단어 개수 파악
3. 최대/최소를 뽑아서 형식에 맞게 return

1번 부분: 퍼즐의 알파벳들로 단어A를 만들 수 있는지? 단어A의 문자 루프 돌면서 그게 퍼즐에 없거나 퍼즐보다 더 많이 있다면 못 만듦.

    for word in words:
        p = True
        word = build_counter(word)
        for char in word:
            if char not in tgt or word[char]>tgt[char]:
                p = False
                break
        if not p: continue
        possible.append(word)

2번 부분: 알파벳 하나씩 퍼즐 중앙에 놨을 때 그 알파벳 꼭 포함해야 하므로 가능한 단어들 중 그 알파벳이 포함되지 않은 단어들을 빼줘야 함. 가능한 단어만 count를 올려주었음.

    for char in tgt:
        temp = 0
        for word in possible:
            if char not in word: # 중간 문자는 꼭 포함해야 하므로.
                continue
            temp += 1
        ans[char] = temp

나머지 풀 코드는 github 에서 확인 가능.