[Python][SWEA] 9480. 민정이와 광직이의 알파벳 공부 D3

SW Expert Academy

 

---

🗒️ 파이썬 코드 풀이

def Alphabet_combination(n,lst_union):
    global ans
    if n == N :
        if lst_union == alphabet:
            ans+=1
        return

    Alphabet_combination(n+1,lst_union|set(lst[n]))
    Alphabet_combination(n+1,lst_union)

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    lst = [set(input().strip()) for _ in range(N)]
    alphabet = set(chr(i) for i in range(ord("a"), ord("z")+1))
    ans = n = 0
    lst_union = set()
    Alphabet_combination(n,lst_union)

    print(f"#{tc} {ans}")

 

1. N의 최대 크기가 15이다. 이 정도의 크기는 완전탐색을 생각해도 괜찮다.

 

2. set (집합) 방식으로 이 문제를 푼다. (중복 제거가 편하기 때문에)

(set 함수는 해시 테이블 기반으로 하여 중복을 빠르게 제거한다.)

 

3. alphabet을 a~z까지 집합으로 만들어준다.  (아스키코드로 반복문 돌려도 되고 노가다 해도 지장없다.)

 

4. lst_union에 완전탐색으로 얻은 집합들을 넣어준다.

 

5. lst_union과 alphabet을 비교해준다. (집합에는 순서가 없음)

 

6. 조건에 충족하면 ans +1 

 

 

📌 나의 풀이 방식

def Alphabet_combination(n,voca_sum):
    global ans

    voca_sum_lst.append(voca_sum)
    if n == N :
        return

    Alphabet_combination(n+1, voca_sum+lst[n])
    Alphabet_combination(n+1, voca_sum)

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    lst = [input().strip() for _ in range(N)]

    alphabet = []  # a~z까지 알파벳 리스트 생성
    for alpha_num in range(ord("a"), ord("z") + 1):
        alphabet.append(chr(alpha_num))


    voca_sum_lst = []
    ans = n = 0
    voca_sum = ""
    Alphabet_combination(n, voca_sum)

    v_sum_lst= list(set(voca_sum_lst))

    for voca in v_sum_lst :
        v_tmp = list(set(voca))
        v = sorted(v_tmp)
        if v == alphabet :
            ans += 1
    print(f"#{tc} {ans}")

 

 재귀함수에서 append를 써주고, 이후  해당 리스트를 집합으로 바꿔주었다. (메모리 비효율성 up)

이후 반복문을 돌리고, 부분 리스트들을 또 집합으로 바꾸고 다시 리스트로 바꿔주었다.

그리고 정렬을 하고 alphabet과 비교를 했다.

 

이렇게 집합을 제대로 쓰지 않아서, 안돌려도 될 반복문을 돌리고, 정렬까지해서 시간복잡도가 증가했다.

중복관련 문제는 집합으로 해결 할 수 있는 방법을 생각해보자.

 

( | : 합집합 (중복 없이) ,  add : 집합끼리 더해줌, & : 교집합, -  : 차집합) 

 

🧐 문제 코멘트

완전탐색의 접근까지는 괜찮았다. 

문제는 strip()을 안써서, 에러 수정에 꽤나 고생했다. 문자열 입력을 받을때 양끝에 불필요한 공백이 있을 수 있으니, 꼭 strip을 통해 공백을 제거해주자.  이번에 얻은 큰 교훈이다...

 

그리고 재귀함수에서 if문을 사용해 voca_sum_lst에 vaca_sum이 있으면, append를 하지않도록 했는데 시간초과가 떳다. 

재귀함수 내부에서는 왠만하면 불필요한 코드를 넣지말고, 재귀함수 외부에서 해결하자.

---

📚 문제

 

아기 광직이는 열심히 받아쓰기를 했지만, 아직 알파벳을 다 떼지 못했다.

아기 민정이는 그런 광직이가 반 친구들에게 놀림 받지 않을까 걱정이 되어 직접 학습지를 만들어 광직이에게 알파벳을 가르쳐 주려고 한다.

(아기 민정이는 광직이보다 동생이지만, 알파벳을 잘 알고 있다.)

민정이는 광직이가 따라 적을 수 있도록 알파벳 연습용 단어 세트를 여러 개 만들 것이다.

광직이는 현재 N개의 영어 단어를 알고 있고, 이 중 몇 개를 골라 하나의 세트로 만드는데, 각 세트 안에 포함된 단어의 순서는 중요하지 않다.

광직이가 모든 알파벳을 골고루 공부할 수 있도록, 단어 세트에는 26개의 알파벳 소문자가 모두 포함되어 있어야 한다.

즉, 모든 알파벳 소문자에 대해, 단어 세트 안에 그 문자를 포함하는 단어가 적어도 하나 존재해야 한다.

단어 세트가 많이 있을수록 광직이가 알파벳을 더 잘 외울 것이라 생각한 민정이는 서로 다른 세트를 최대한 많이 만들어 주려고 한다.

아기 민정이가 광직이를 위해 몇 개의 단어 세트를 만들 수 있을지 구해주자!

[입력]

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.

이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다.

각 테스트 케이스는 다음과 같이 구성되어 있다.

> 첫 번째 줄에 아기 민정이가 아는 단어의 개수 N이 주어진다. (1 <= N <= 15) 

> 이후 N개의 줄에 민정이가 아는 단어들이 한 줄에 하나씩 주어진다.

> 각 단어는 공백 없이 알파벳 소문자로만 이루어져 있다.

> 단어 하나의 길이는 1이상 100이하 이며, 모든 단어는 서로 다르다.

[출력]

각 테스트 케이스마다 ‘#t’(t 는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

민정이가 만들 수 있는 서로 다른 단어 세트의 개수를 출력한다.