[BOJ1148] 단어 만들기

문제

• 3*3 표에 영문자 하나씩, 최대한 많은 영단어 만들기
• 한 글자당 최대 한 번만 사용, 단어 길이 4 ~ 9
• 표 정중앙에 있는 글자 반드시 사용
• 중앙에 어떤 수를 놓아야 퍼즐이 가장 쉬워지고, 어려워지는지 구하기

입력

• 사전 최대 20만 개
• 각 단어 4 ~ 9글자
• ’-‘ 사전 끝
• 퍼즐판 9개 영어 대문자로
• ’#’ 퍼즐 끝

출력

• 각 문제마다 정답의 개수를 가장 적게 하기 위해 정중앙에 놓아야 할 문자들과 그때의 정답 개수, 정답의 개수를 가장 많게 하기 위해 정중앙에 놓아야 할 문자들과 그 때의 정답 개수를 공백으로 구분하여 출력

• 한 개 이상의 문자가 답을 만족할 경우 문자들을 알파벳순으로 정렬하여 출력하며, 중복된 문자는 출력 금지

설계

• 사전에 해당하는 단어들의 각 알파벳 수를 dictionary에 저장
• 퍼즐판 알파벳 수를 words에 저장
• dictionary를 돌면서 words보다 알파벳 수가 적은 경우 조합 가능한 단어
• 조합 가능한 단어의 알파벳은 ret 배열에서 하나씩 증가
• 알파벳을 순회하며 ret배열을 기준으로 최소 최대 구하기

How I solved(click to github)

---

ref :
BOJ1148