단어 만들기 ( 1148 번 )

1148번: 단어 만들기

 

---

🧠 알고리즘

• 문자 퍼즐 완성 가능 여부를 Counter(해시맵) 으로 체크하고, 각 퍼즐이 만들 수 있는 단어들에 대해 최소/최대 빈도 문자를 탐색하는 방식

 

✔️ 동작 방식

• 각 퍼즐에 대해 후보 단어들이 퍼즐로 만들 수 있는지 _ava_check 로 확인
• 퍼즐의 알파벳 하나하나가 후보 단어 집합들에 몇 개 포함되는지 세어 빈도를 기록
• 가장 적게 등장하는 알파벳들과, 가장 많이 등장하는 알파벳들을 정렬해 출력
• 최종적으로 퍼즐별 "최소빈도문자 min개수 최대빈도문자 max개수" 형태로 출력

---

 

🧾 코드

import sys
from collections import Counter

def _mk():
    a1, a2 = [], []
    type = 1
    while True:
        now_str = sys.stdin.readline().rstrip()
        if now_str == '-':
            type = 2
            continue
        if now_str == '#':
            break

        if type == 1:
            a1.append(Counter(now_str))
        else:
            a2.append(Counter(now_str))

    return a1, a2


def _ava_check(pz, ct): # 못 만들면 False,,,
    for k, v in ct.items():
        if (k not in pz) or (pz[k] < v):
            return False
    return True


def _result(pz, ct): # 만들수 있는 min, max 단어 return
    answer = {}
    for i in pz:
        count = sum(1 for j in ct if i in j)
        if count in answer:
            answer[count].append(i)
        else:
            answer[count] = [i]

    n, m = min(answer.keys()), max(answer.keys())
    return f"{''.join(sorted(answer[n]))} {n} {''.join(sorted(answer[m]))} {m}"
    

def _main(create, pz):
    answer = []
    for now_pz in pz:
        ava_list = []
        for now_ct in create:
            if _ava_check(now_pz, now_ct):
                ava_list.append(set(now_ct.keys()))

        result = _result(set(now_pz.keys()), ava_list)
        answer.append(result)

    return '\n'.join(answer)

create, pz = _mk()
print(_main(create, pz))

---

 

⏱️ 시간 복잡도

for now_pz in pz : 퍼즐을 순회 ( 선형 시간 복잡도 )
	for now_ct in create : 주어진 단어를 순회 ( 선형 시간 복잡도 )
		_ava_check(now_pz, now_ct) : 각 단어 가능 여부 체크 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 삼차형 시간 복잡도 ( O(n ** 3) )