99클럽 코테 스터디 TIL : 72412 순위 검색

🚀 문제

https://school.programmers.co.kr/learn/courses/30/lessons/258712

🚀 정답 코드

🚀 시행착오 했던 부분

def solution(info, query):
    
    info = [i.split(' ') for i in info]
    query  = [ i.replace(" and", "").split(" ") for i in query ]
    answer = [0]*len(query)
    index = 0

    for q, qIndex in zip(query, range(len(query))):
        query_select = q[:-1]
        query_score = int(q[-1])
        
        for row in info:
            info_select = row[:-1]
            info_score = int(row[-1])
            
            correct_query = True
            for v1, v2 in zip(row, query_select):
                if v2 != '-' and v1 != v2:
                    correct_query = False
                    break
                    
            if correct_query and query_score <= info_score:
                answer[qIndex] += 1
    return answer

초반에는 단순 구현 문제라고 느껴졌다. 그래서 위와 같이 먼저 시도해보았지만 정확도 부분은 통과했지만 효율성 부분은 통과하지 못했다.

문제는 3중 for 문에 있다고 생각했고, query와 info를 반복하는 부분은 각 케이스의 개수를 세야하기 때문에 개선하기 어렵다고 생각했고, 두 배열을 비교하는 마지막 배열 부분을 다르게 개선하는 쪽으로 개선 해보았다.

먼저 생각했던 것은 정규 표현식을 통해서 반복문을 사용하지 않고 .findAll을 통해서 개수를 세는 쪽으로 시도해보려고 했는데, 정규 표현식을 사용하는 것이 오히려 더 구현이 복잡하고, 단순 문자열 비교 보다 더많은 시간이 소요된다는 것을 보고 다른 방향을 생각해보았다.

결국 시간이 많이 지나서 다른 답안의 도움을 받았고, info를 기준으로 파생할 수 있는 모든 경우를 dict로 관리 + 쿼리를 만족하는 info의 개수를 이진 탐색(중간값 정리)로 계산하는 방식을 알게 되었다.

백날 생각해고 생각하기 어려운 아이디어라는 느낌이 강한 답안이었다.