Programmers - 순위 검색

문제링크

나의 풀이

def solution(info, query):
    result = [0] * len(query)
    # 입력
    for i in range(len(query)):
        query[i] = query[i].replace(' and', '')
        query[i] = list(query[i].split(' '))
        info[i] = list(info[i].split(' '))
        print(info[i])
    
    # 비교
    for i in range(len(query)):
        for j in range(len(info)):
            if int(info[j][4]) >= int(query[i][4]) and (info[j][0] == query[i][0] or query[i][0] == '-') and (info[j][1] == query[i][1] or query[i][1] == '-') and (info[j][2] == query[i][2] or query[i][2] == '-') and (info[j][3] == query[i][3] or query[i][3] == '-'):
                result[i] += 1
    return result

• 정확도는 통과했지만 효율성에서 통과하지 못했다.

다른 풀이

def solution(info, query):
    data = dict()
    for a in ['cpp', 'java', 'python', '-']:
        for b in ['backend', 'frontend', '-']:
            for c in ['junior', 'senior', '-']:
                for d in ['chicken', 'pizza', '-']:
                    data.setdefault((a, b, c, d), list())
    for i in info:
        i = i.split()
        for a in [i[0], '-']:
            for b in [i[1], '-']:
                for c in [i[2], '-']:
                    for d in [i[3], '-']:
                        data[(a, b, c, d)].append(int(i[4]))

    for k in data:
        data[k].sort()

        # print(k, data[k])

    answer = list()
    for q in query:
        q = q.split()

        pool = data[(q[0], q[2], q[4], q[6])]
        find = int(q[7])
        l = 0
        r = len(pool)
        mid = 0
        while l < r:
            mid = (r+l)//2
            if pool[mid] >= find:
                r = mid
            else:
                l = mid+1
            # print(l, r, mid, answer)
        # answer.append((pool, find, mid))
        answer.append(len(pool)-l)

    return answer

• 효율성에 문제가 있어, 입력받은 데이터를 처리하는 것보다는 데이터를 어떻게 탐색할까에 초점을 맞췄다. 효율성문제가 제일 까다로운 것 같다.
  • 효율성문제 같은 경우는 정형화된 알고리즘을 문제에 적용할 수 있는가를 물어보는 문제인 것 같다. bruteforce로는 안푸는게 최선이다. 퀵정렬, 이진탐색, 백트래킹 등을 활용하도록 처음부터 고민하자.