프로그래머스 - 순위 검색 Lv2 풀이/주석/자세한 설명

포스팅 요약

1. 문제 보러 가기

2. 코드 및 상세 주석

---

1. 문제 보러 가기

프로그래머스: 순위 검색 Lv2:

https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=python3 

 

정확성과 효율성이 모두 필요한 문제입니다.

정확성을 통과하긴 쉬우나 효율성을 통과하기는 어려웠네요 ㅜㅜ

효율성은 다른 사람들의 풀이를 보고 저만의 코드로 작성해 보았습니다.

 

---

2. 코드 및 주석

첫 번째 코드

정확성: 통과 , 효율성: 실패

import re

def findPerson(info,query):
    cnt=0
    for i in info:
        for j in range(5):
            if j!=4:
                if i[j]==query[j] or query[j]=="-":
                    continue
            else:
                if int(i[j])>=int(query[j]) or query[j]=="-":
                    cnt+=1
                    continue
            break   
    return cnt
        

def solution(info, query):
    answer =[]
    
    info_list=[i.split() for i in info]
    query_list=[re.split(' and | ',i) for i in query]
    
    for i in query_list:
        answer.append(findPerson(info_list,i))
    
    return answer

 

코드 설명: info리스트와 query리스트를 for문으로 순회하며 비교한 코드입니다.

정확성은 100% 통과였지만 효율성이 좋지 않아 불통 ㅠㅠ

---

정확성: 통과 , 효율성: 통과

import re
from bisect import bisect_left
from itertools import combinations

def dictionary_info(info):
    dic={}
    for i in info:
        
        lst_key=i[:-1]
        lst_value=int(i[-1])
        
        for j in range(5):
            for c in combinations(lst_key,j):
                key="".join(c)
                if key in dic:
                    dic[key].append(lst_value)
                else:
                    dic[key]=[lst_value]
    
    for i in dic:
        dic[i].sort()
    return dic
        
        
def solution(info, query):
    answer = []
    info_list=[i.split() for i in info] 
    query_list=[re.split(' and | ',i) for i in query]
    
    
    info_dict=dictionary_info(info_list)
    for i in query_list:
        while "-" in i: i.remove("-")
        lst_key="".join((i[:-1]))
        lst_score=int(i[-1])
        
        if lst_key in info_dict:
            dic_score=info_dict[lst_key]
            cnt=len(dic_score)-bisect_left(dic_score,lst_score)
            answer.append(cnt)
        else:
            answer.append(0)
    
    
    return answer

 

주석 달린 코드

import re
from bisect import bisect_left
from itertools import combinations

def dictionary_info(info):
    dic={}
    
    #4
    for i in info:
        
        lst_key=i[:-1] #점수를 제외한 값들의 리스트 생성
        lst_value=int(i[-1]) #해당 info 리스트 에서의 점수
        
        # 예 1-1) i=["java","backend","junior","pizza","150"]
        # lst_key=["java","backend","junior","pizza"]
        # lst_value=150
        
        for j in range(5):
            for c in combinations(lst_key,j): # 나올 수 있는 조합을 모두 생성
            
            # 쉽게 설명하자면, query 리스트에서 ["-","-","junior","-","150"]를 찾을때
            # info리스트에서 junior 그리고 코테 150점 이상인 사람이면 다 조건에 부합한다.
            # 예 1-1 에서 i=["java","backend","junior","pizza","150"]은
            # query=["-","-","-","-","150"]이 있을때 통과되고,
            # query=["java","-","-","-","150"]이 있을때 통과되고, 
            # query=["java","backend","-","-","150"]이 있을때 통과되고,
            # ... 일때 통과된다.
            
            #그래서 query가 나올 수 있는 모든 경우의 수를 다 조합하는 것이다.
            
                key="".join(c)
                if key in dic:
                    dic[key].append(lst_value)
                else:
                    dic[key]=[lst_value]
    for i in dic:
        dic[i].sort()
    return dic
        
        
def solution(info, query):
    answer = []
    
    #1
    info_list=[i.split() for i in info] #공백 기준으로 나눠서 리스트타입으로 만들어줌
    
    #2
    query_list=[re.split(' and | ',i) for i in query] 
   	#and와 공백 기준으로 나눠서 리스트타입으로 만들어줌
    
    #3
    info_dict=dictionary_info(info_list) #조건에 맞는 값을 찾기 위한 딕셔너리 생성
    
    #info_dict은 아래와 같은 형식으로 출력된다.
    #info_dict = {'': [50, 80, 150, 150, 210, 260], 'java': [80, 150],
    #'backend': [50, 80, 150, 260], 'junior': [80, 150], 
    #'pizza': [150, 260], 'javabackend': [80, 150], 
    #'javajunior': [80, 150], 'javapizza': [150], 
    #'backendjunior': [80, 150], 'backendpizza': [150, 260], 
    #'juniorpizza': [150] ... ...}
    
    #5
    for i in query_list:
    	# 예) i:['java', 'backend', 'junior', '-', '100']
        
        while "-" in i: i.remove("-")
        # i:['java', 'backend', 'junior', '100']
        
        lst_key="".join((i[:-1])) # lst_key="javabackendjunior"
        lst_score=int(i[-1]) # lst_score=100
        
        if lst_key in info_dict: #lst_key가 info_dict 키값 중에 존재한다면
            dic_score=info_dict[lst_key] #해당 info_dict의 value값을 가져옴
            
            cnt=len(dic_score)-bisect_left(dic_score,lst_score)
			# bisect_left를 사용하여 index값을 없고
           	# dic_score의 길이에서 index값을 빼주면 조건에 만족하는 info개수 출력            

            answer.append(cnt)
        else: #lst_key가 info_dict 키값 중에 존재하지 않으면 0개 리턴
            answer.append(0)
    
    
    return answer

bisect과 combinations를 사용한 풀이입니다. 

 

그리고, bisect 사용법을 모르신다면 아래 블로그 추천 드립니다.

해당 블로그에서는 bisect 사용법에 대해 간략하고 이해하기 쉽게 잘 정리되어 있습니다.

코딩님의 블로그: https://ssooyn.tistory.com/11