[python][2021 KAKAO BLIND RECRUITMENT] 순위 검색

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

문자열(string)을 리스트로!

examplestring="java and backend and junior and pizza 100"
print(examplestring.split())

examplestring="java and backend and junior and pizza 100"
print(examplestring.split('and'))

    examplestring="java and backend and junior and pizza 100"
    exlist = examplestring.split(' ')
    while 'and' in exlist:
        exlist.remove('and')

if 조건문 여러줄로!

            if (
                (tmp[0] == '-' or tmp[0] == infolist[j][0]) and
                (tmp[1] == '-' or tmp[1] == infolist[j][1]) and
                (tmp[2] == '-' or tmp[2] == infolist[j][2]) and
                (tmp[3] == '-' or tmp[3] == infolist[j][3]) and
                (int(tmp[4]) <= int(infolist[j][4]))
            ):

 

1차 코드 결과(효율성 테스트 탈락)

def solution(info, query):
    answer = []    
    infolist=[]
    
    #info 전체 데이터 리스트로 정리
    for i in info:
        infolist.append(i.split(' '))
    
    #query 한문장씩 정리
    for i in query:
        count=0
        tmp=i.split(' ')
        while 'and' in tmp:
            tmp.remove('and')
        
        #전체 데이터 조건 전체 맞는 것 구분
        for j in range(len(infolist)):
            
            if (
                (tmp[0] == '-' or tmp[0] == infolist[j][0]) and
                (tmp[1] == '-' or tmp[1] == infolist[j][1]) and
                (tmp[2] == '-' or tmp[2] == infolist[j][2]) and
                (tmp[3] == '-' or tmp[3] == infolist[j][3]) and
                (int(tmp[4]) <= int(infolist[j][4]))
            ):
                count+=1
        
        answer.append(count)        
    
    return answer

 

2차원 배열 정렬!

    infolist.sort(key=lambda x:(-int(x[4])))
    #infolist.sort(key=lambda x:(-int(x[4]), x[1], x[2], x[3], x[0]))

숫자에 대해서만 정렬을 해서 해당 수보다 커지면 더이상 검색 안하는 방식!

실패!(느리다. 정렬하는 시간이 더 길다.)

 

2차 정렬된 데이터로 확인 코드 결과(효율성 테스트 탈락)

def solution(info, query):
    answer = []    
    infolist=[]
    
    #info 전체 데이터 리스트로 정리
    for i in range(len(info)):
        infolist.append(info[i].split(' '))
        infolist[i][4]=int(infolist[i][4])
    infolist.sort(key=lambda x:(-(x[4])))
        
    #query 한문장씩 정리
    for i in query:
        count=0
        tmp=i.split(' ')
        while 'and' in tmp:
            tmp.remove('and')
        tmp[4]=int(tmp[4])
            
        #전체 데이터 조건 전체 맞는 것 구분
        for j in range(len(infolist)):
            
            if (tmp[4] <= infolist[j][4]):    
                if (
                    (tmp[0] == '-' or tmp[0] == infolist[j][0]) and
                    (tmp[1] == '-' or tmp[1] == infolist[j][1]) and
                    (tmp[2] == '-' or tmp[2] == infolist[j][2]) and
                    (tmp[3] == '-' or tmp[3] == infolist[j][3])
                ):
                    count+=1
            else :
                break
        
        answer.append(count)        
    
    return answer

효율성이 약간은 좋아졌다!

문자열에서 해당 문자 찾기 in!

tmp[0] in infostring

 

3-1차 문자열내 해당 문자들 존재여부 확인 코드 결과(효율성 테스트 탈락)

import re
def solution(info, query):
    answer = []
        
    #query 한문장씩 정리
    for i in query:
        count=0
        tmp=i.split(' ')
        while 'and' in tmp:
            tmp.remove('and')
        
        #info 문자열 리스트에서 해당 문자들 찾기
        for infostring in info:

            if (
                (tmp[0] == '-' or tmp[0] in infostring) and
                (tmp[1] == '-' or tmp[1] in infostring) and
                (tmp[2] == '-' or tmp[2] in infostring) and
                (tmp[3] == '-' or tmp[3] in infostring) and
                (int(tmp[4]) <= int(re.sub(r'[^0-9]', '', infostring)))
            ):
                count+=1

        answer.append(count) 
    
    return answer

효율성 더 안좋아짐...

후... 효율성 미치겠네...

3-2차 문자열내 해당 문자들 존재여부 확인 코드 결과(효율성 테스트 탈락)

def solution(info, query):
    answer = []
        
    #query 한문장씩 정리
    for i in query:
        count=0
        tmp=i.split(' ')
        while 'and' in tmp:
            tmp.remove('and')
        
        #info 문자열 리스트에서 해당 문자들 찾기
        for infostring in info:

            if (
                (tmp[0] == '-' or tmp[0] in infostring) and
                (tmp[1] == '-' or tmp[1] in infostring) and
                (tmp[2] == '-' or tmp[2] in infostring) and
                (tmp[3] == '-' or tmp[3] in infostring) 
            ):

                if (int(tmp[4]) <= int(''.join(filter(str.isdigit, infostring)))):
                    count+=1

        answer.append(count) 
    
    return answer

검색 방법을 바꿔보자!

이진검색(binary search)을 이용해보자.

[알고리즘] 이진 검색 - Binary Search (Python, Java)

이미 다른 올라온 답도 있다.

[Python] 프로그래머스(Lv2) - 순위검색 (2021 KAKAO BLIND RECRUITMENT)

4차 Dictionary를 이용한 이진검색 알고리즘 코드 결과(정답!)

def solution(info, query):
    
    answer = []
    checkdata = {}
    infoslit = []
    
    #나올 수 있는 전체 경우의 수를 dictionary로 만든다.
    for a in ['cpp', 'java', 'python', '-']:
        for b in ['backend', 'frontend', '-']:
            for c in ['junior', 'senior', '-']:
                for d in ['chicken', 'pizza', '-']:
                    checkdata.setdefault((a, b, c, d), list())
    
    #info에 숫자값을 뽑아 전체에서 속할 수 있는 곳에 value값으로 준다.
    for i in info:
        infolist = i.split(' ')
        for a in [infolist[0], '-']:
            for b in [infolist[1], '-']:
                for c in [infolist[2], '-']:
                    for d in [infolist[3], '-']:
                        checkdata[(a, b, c, d)].append(int(infolist[4]))
    
    #전체 dictionary에서 value값을 정렬해준다.
    for i in checkdata:
        checkdata[i].sort()
    
    for i in query:
        tmp=i.split(' ')
        while 'and' in tmp:
            tmp.remove('and')
        tmp[4]=int(tmp[4])
        
        pool = checkdata[(tmp[0],tmp[1],tmp[2],tmp[3])]
        find = int(tmp[4])
        
        l = 0
        r = len(pool)
        mid = 0
        while l < r:
            mid = (r+l)//2
            if pool[mid] >= find:
                r = mid
            else:
                l = mid+1
        answer.append(len(pool)-l)

    return answer