카카오 2021 순위 검색 파이썬 코드/풀이 (Lv 2 라기에는 너무 어려운 문제)

깃허브에서 코드만 볼 분은 링크 눌러주세요!

GitHub - Rhyankwon/algorithms

 

 

문제 설명 ㄱㄱ

코딩테스트 연습 - 순위 검색

문제 자체는 상당히 간단하다. 일련의 정보들이 나열된 info가 주어지는데 각 정보들의 교집합을 만족하는 사람의 숫자를 리턴하면 된다. 근데 효율성 테스트가 있어서.. 이게 진짜 lv2라고?ㅋㅋㅋㅋㅋㅋ싶다. 효율성을 빼면 lv1이고 효율성 끼면 lv3짜리.

 

 

문제 해설..은 두가지 버전이 있는데,

 

우선 나는 java, python, junior 등등 각각을 만족하는 사람(인덱스)을 set에 저장한 딕셔너리를 만들고

 

그 set끼리 교집합해서 우선 점수를 제외하고는 조건을 만족하는 인덱스 풀을 만들었다.

 

그리고 미리 인덱스랑 점수를 따로 저장해서 sort한 후 거기에서 또 점수를 만족하는 인원만 슬라이싱해서 집합으로 바꿔서 다시 교집합 ...

 

ㅋㅋㅋㅋㅋㅋㅋㅋ논리연산자를 상당히 많이 활용했는데 역시나 효율성은 통과할 수 없었다.

 

 

 

결국 카카오 풀이를 보고 풀었다. 카카오에서는 어떻게 풀었냐면, 만약 cpp, backend, senior, pizza, 260이렇게 있으면 cpp - - -, cpp backend - -, - backend --, 이런식으로 -를 껴서 만들 수 있는 모든 경우에 대해 딕셔너리를 만들었다. 이 때에는 나중에 점수컷을 해야하므로 각 인덱스가 아니라 각 숫자를 리스트에 저장하고 모든 과정이 끝나면 숫자를 sort한다. --> 이 부분도 실제로 구현해보면 쉽지 않음.... for문이 네개나 들어가고 사이에 combinations도 써야하고. 

 

그러면 이제 query부분에서는 단순히 들어온 단어들을 조합해서 붙여서 dict에 key로 써서 찾으면 된다. 그러면 이제 점수컷을 해야하는데, 아까 숫자들을 sort해서 저장해놨으니까 bisect_left를 써서 조건을 만족하는 인덱스를 찾고 전체 길이에서 그 인덱스만큼 빼면 조건을 만족하는 사람 수만 정확히 나오게 된다.

 

    for origin_q in query:
        origin_q = origin_q.split()
        tmp_q = ''.join([i for i in origin_q[:-1] if i != 'and'])
        if tmp_q not in cases:
            answer.append(0)
        else:
            cand = cases[tmp_q]
            b = bisect.bisect_left(cand, int(origin_q[-1]))
           # b = bisect.bisect_left(list(cand), int(origin_q[-1])) 불가!
            answer.append(len(cand)-b)

지금 보면 list 저거 하나 사이에 넣었다고 또 효율성 통과를 못해서..ㅋㅋㅋ 수정에 수정에 수정을 반복했다. 아 참고로 bisect 저거는 이진탐색을 안 하면 또 안 풀려서 ..ㅎㅎ 무조건 bisect를 써야한다. 아니면 start, end 지정해서 찾던가 ...

 

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ이게 말이 쉽지 ...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ풀이를 봐도 구현이 상당히 까다롭다. 그리고 아무래도 먼저 풀던 과정이 있다보니까 풀이를 보고도 그 구현방법을 생각해내는게 그렇게 쉽지가 않아서 더 헤맸다. 진짜 종일 풀었다는 말이 맞을 정도로 오래 걸렸다. 최소 5~6시간 소요한듯. 남의 풀이를 보고 내껄로 다시 만들고 싶어서 계속 고민했는데,, 힘들었다.