파이썬) 카카오 - 가사 검색 문제 풀이

bisect - 이진 탐색

---

bisect 모듈은 이진 탐색 알고리즘을 구현한 모듈이다. bisect.bisect 함수는 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 리턴한다.

문제

A 학급의 학생수는 총 7명이다. 7명의 성적은 다음과 같다.

[33, 99, 77, 70, 89, 90, 100]

그리고 성적에 대한 학점은 다음과 같은 기준으로 정해진다.

• 90점 이상 : A
• 80점 이상 : B
• 70점 이상 : C
• 60점 이상 : D
• 0~59점 : F

A학급 학생들의 학점을 순서대로 구하시오.

풀이

보통 이런류의 문제는 if else를 이용한 분기문으로 풀이하지만 bisect.bisect 함수를 사용하면 보다 우아하고 간결하게 문제를 풀수 있다.

다음과 같이 코드를 작성해 보자.

[파일명:bisect_sample.py]

import bisect

result = []
for score in [33, 99, 77, 70, 89, 90, 100]:
    pos = bisect.bisect([60, 70, 80, 90], score)  # 점수가 정렬되어 삽입될 수 있는 포지션을 반환
    grade = 'FDCBA'[pos]
    result.append(grade)

print(result)

위 코드를 실행한 출력결과는 다음과 같다.

['F', 'A', 'C', 'C', 'B', 'A', 'A']

bisect.bisect([60, 70, 80, 90], score) 에서 bisect함수는 [60, 70, 80, 90] 에서 score가 정렬되어 삽입될 수 있는 인덱스를 리턴한다. 예를 들어 85점이라면 80과 90 사이인 3을 리턴한다.

70점과 90점과 같이 학점을 구분하는 점수와 동일한 경우 bisect 함수는 좌측이 아닌 우측으로 삽입되는 인덱스를 반환한다.

그런데 만약 학점의 기준이 다음과 같이 변경된다면 어떻게 해야 할까?

• 90점 초과 : A
• 80점 초과 : B
• 70점 초과 : C
• 60점 초과 : D
• 0~60점 : F

학점의 기준이 위와 같이 "이상"에서 "초과"로 변경된다면 80점인 경우 B가 아닌 C가 되어야 한다. 이런 경우에는 다음처럼 bisect함수 대신 bisect_left 함수를 사용할 수 있다.

import bisect

result = []
for score in [33, 99, 77, 70, 89, 90, 100]:
    pos = bisect.bisect_left([60, 70, 80, 90], score)
    grade = 'FDCBA'[pos]
    result.append(grade)

print(result)

출력 결과는 다음과 같다.

['F', 'A', 'C', 'D', 'B', 'B', 'A']

성적이 70점인 경우 D학점, 90점인 경우 B학점으로 나온다.

bisect대신 bisect_left를 사용하면 점수가 학점을 구분하는 리스트([60, 70, 80, 90])의 요소 값과 동일할 경우(예:70점, 90점) 삽입되는 위치가 우측이 아닌 좌측이 된다. 즉, 점수가 70점인 경우 삽입 위치가 2가 아닌 1이 된다.

bisect 함수는 bisect_right 함수와 동일하다. 즉, bisect 대신 bisect_right 함수를 사용해도 된다.

bisect.insort

bisect.insort 는 정렬될 수 있는 위치에 해당 항목을 삽입한다.

>>> import bisect
>>> a = [60, 70, 80, 90]
>>> bisect.insort(a, 85)
>>> a
[60, 70, 80, 85, 90]

참고

• 이진 검색 알고리즘(위키백과)
• https://docs.python.org/ko/3/library/bisect.html

bisect — 배열 이진 분할 알고리즘 — Python 3.10.2 문서

 

---

https://programmers.co.kr/learn/courses/30/lessons/60060

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

• 가사 검색

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

wordsqueriesresult

["frodo", "front", "frost", "frozen", "frame", "kakao"]

["fro??", "????o", "fr???", "fro???", "pro?"]

[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

---

시간 복잡도에 걸려 풀지 못하였는데 이문제를 bisect를 이용하면 정답이 나온다.

먼저 이분탐색을 하기 위해서라면 정렬이 돼있다는 조건이 있어야 한다. 

 

from bisect import bisect_left, bisect_right

arr = [[] for _ in range(100001)]
reversed_arr = [[] for _ in range(100001)]

def bisect_result(word_arr, X, Y):
    first = bisect_left(word_arr, X)
    second = bisect_right(word_arr, Y)
    return second - first

def solution(words, queries):
    answer = []
    
    for word in words:
        arr[len(word)].append(word)
        reversed_arr[len(word)].append(word[::-1])
    
    for i in range(len(arr)):
        if len(arr[i]) == 0:
            continue
        sorted_word = arr[i]
        sorted_word.sort()
        arr[i] = sorted_word
        
        sorted_word_revered = reversed_arr[i]
        sorted_word_revered.sort()
        reversed_arr[i] = sorted_word_revered
    
    for query in queries:
        if query[0] == '?':
            query_reverse = query[::-1] 
            ans = bisect_result(reversed_arr[len(query)], query_reverse.replace('?', 'a'), query_reverse.replace('?', 'z'))
        else:
            ans = bisect_result(arr[len(query)], query.replace('?','a'), query.replace('?','z'))
        answer.append(ans)
    return answer

 

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.

이조건을 활용하여 100001개의 배열이 담긴 word 각 길이에 맞는 배열의 위치에 word를 담을 arr과 뒤집힌 word가 담길 revered_arr을 선언하여 주었다. 여기서 뒤집힌 word를 담아주는 이유는 '?rodo'와 같이  '?'가 앞에 위치하는 경우를 대비하여 만들어준것이다.

biscet를 통해 간단하게 풀어보았다.