[프로그래머스] 가사 검색

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

초기에 문제를 접하였을때, 가사를 하나씩 반복하며 나올 수 있는 모든 경우의 수를 키로 만들어서 카운트 하였습니다.

그러나 효율성의 5개 중 3개만 통과하고 2개를 통과하지 못하였습니다.

 

Trie(트라이) 라는 자료 구조를 알게 되어, 딕셔너리를 이용하여 만들었습니다.

물음표가 앞 또는 뒤에서만 나오기 때문에 앞과 뒤를 저장해두는 두개의 딕셔너리를 생성하였습니다.

각 딕셔너리의 최상단에는 글자 수를 키로 가지는 딕셔너리입니다.

글자 수 안에는 내부에 다음 글자를 키로 가지는 딕셔너리가 존재하게 됩니다.

2) 알고리즘

• Trie

3) 풀이 코드

사용 언어 - Python

def solution(words, queries):
    start = {}                                          # 앞에 ? 가 붙은 경우를 저장
    end = {}                                            # 뒤에 ? 가 붙은 경우를 저장
    answer = []                                         # 정답 리스트 변수

    for word in words:                                  # 단어를 저장
        n = len(word)                                   # 단어의 길이
        
        if not start.get(n, False):                     # 현재 길이가 단어들이 없으면 새로운 객체 생성
            start[n] = {'cnt': 1}
            end[n] = {'cnt': 1}
        else:                                           # 현재 길이의 단어들이 기록되어 있으면 단어 카운트 증가
            start[n]['cnt'] += 1
            end[n]['cnt'] += 1

        start_dict = start[n]                           # 내부 객체
        end_dict = end[n]
        for i in range(n):                              # 단어 한글자씩 반복
            start_c = word[i]                           # 앞글자
            end_c = word[n-i-1]                         # 뒷글자

            if not start_dict.get(start_c, False):      # 동일한 글자가 나온적이 없으면, 객체 생성
                start_dict[start_c] = {'cnt': 1}
            else:
                start_dict[start_c]['cnt'] += 1         # 나온적 있으면 카운트 증가

            if not end_dict.get(end_c, False):
                end_dict[end_c] = {'cnt': 1}
            else:
                end_dict[end_c]['cnt'] += 1
            
            start_dict = start_dict[start_c]            # 다음 내부 탐색을 위함
            end_dict = end_dict[end_c]
    

    for query in queries:                               
        if query[0] == '?':                             # 앞에 ? 가 있는 경우
            query = query[::-1]                         # 단어 뒤집기
            if end.get(len(query), False):              
                end_dict = end[len(query)]
            else:                                       # 해당 글자수가 없으면
                answer.append(0)                        # 0 반환
                continue

            cnt = end[len(query)]['cnt']                # 해당 글자수의 단어 개수 초기 정의
            end_dict = end[len(query)]                  # 내부 객체
            for q in query:
                if end_dict.get(q, False):              # 다음 글자가 있는 경우
                    cnt = end_dict[q]['cnt']            # 개수 저장
                    end_dict = end_dict[q]              # 내부 객체 조회 위함
                else:
                    if q == '?':            
                        answer.append(cnt)              # 현재 글자가 ? 라면, 저장된 개수 반환
                    else:
                        answer.append(0)                # 해당 문자가 아예 없으면 0 반환
                    break

        else:
            if start.get(len(query), False):
                start_dict = start[len(query)]
            else:
                answer.append(0)
                continue

            cnt = start[len(query)]['cnt']
            for q in query:
                if start_dict.get(q, False):
                    cnt = start_dict[q]['cnt']
                    start_dict = start_dict[q]
                else:
                    if q == '?':
                        answer.append(cnt)
                    else:
                        answer.append(0)
                    break
                
    return answer

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/60060?language=python3 

코딩테스트 연습 - 가사 검색

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다