[프로그래머스] 순위 검색

겪은문제

• 문자열을 쿼리에 맞게 파싱하여 조건에 맞게 구현하는 문제로 생각해서 풀면 대략 아래와 같은 코드와 아래와 같은 결과를 얻을 수 있음

def solution(info, query):
    answer = [0] * len(query)
    people_info = []
    parsing_query = []
    query_info = [("cpp", "java", "python"),("backend", "frontend"),
    				("junior", "senior"), ("chicken", "pizza")]
    
    # 사람 정보 파싱
    for temp in info:
        language, position, career, soulfood, score = temp.split()
        people_info.append((language, position, career, soulfood, score))
    
    # 쿼리 정보 파싱
    for qu in query:
        q = qu.split()
        for i in range(0, 7, 2):
            if q[i] == '-':
                q[i] = query_info[i // 2]
        parsing_query.append((q[0], q[2], q[4], q[6], q[7]))

    # 쿼리 정보에 일치하는 사람인지 카운트
    for i in range(len(parsing_query)):
        for j in range(len(people_info)):
            if people_info[j][0] in parsing_query[i][0] and
            	people_info[j][1] in parsing_query[i][1] and 
                people_info[j][2] in parsing_query[i][2] and 
                people_info[j][3] in parsing_query[i][3] and 
                int(people_info[j][4]) >= int(parsing_query[i][4]):
                
                answer[i] += 1

               
    return answer

응..? 뭐가 문제지?

문제 설명

• info 배열의 크기는 1 이상 50,000 이하입니다. 여기서 아이디어를 얻어보면 사람정보는 최대 5만으로 하나의 조건을 볼때마다 5만번씩 도는 비효율 적인 결과를 얻게 된다.
• 시간 초과를 해결하기 위해 필요하지 않은 것을 돌지 않게 만들어 주려면 사람별로 조건을 key로 사용하고 점수를 value로 사용한다.
• 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다. 이 부분에서 우리는 O(n)보다 작은 방법을 찾아야 한다. 이 부분은 이분탐색을 활용하면 해결 가능하다.

정답 코드는 여기서