[프로그래머스] 순위 검색 (Level2) (Python)

문제 출처 :

https://programmers.co.kr/learn/courses/30/lessons/72412

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

문제 풀이 :

• 카카오 기출인 만큼 문제 설명이 따로 필요 없을 정도로 문제가 상세하게 잘 설명되어있다.
• 본인의 경우 2가지 부분에서 조금 애를 먹었다.
  • 런타임에러
  • 효율성 검사
• 런타임에러
  • 런타임 에러 같은 경우는 query에서 받은 값을 food 와 score로 분해해야되는데 왜 그랬는지 모르겟지만 점수가 3자리라고 생각해서 인덱싱을 잘못 넣어서 생기는 문제였다.
  • 추가로 찾아보니 python에서 dict을 사용해서 문제를 풀 경우 key값이 존재 하지 않는 경우를 처리해주어야 된다고 한다.
• 효율성 검사
  • 카카오문제에서 효율성 검사가 잇다는 것은 무지성으로 코딩하라는 뜻이 아니라 효율적인 알고리즘을 쓰라는 뜻이다.
  • 이 문제에서 알고리즘 적으로 효율성을 높일 수 있는 방법이 뭐가 있을까 고민하다가 score에서 이상 인 부분임을 알게 되었고 이부분에서 한참 고민하다가 탐색 알고리즘 중에 이분탐색을 쓰면 된다는 것을 알게 되었다. ( 이정도도 캐치를 못하는게 아직도 멀었다는 생각이 든다.)
  • python의 경우 기본 라이브러리인 bisect 라이브러리를 사용하면 직접 짜지 않고도 쉽게 이용 할 수 잇다.
• 기본적으로 코드의 큰 틀은 언어, 직군, 경력, 소울푸드 를 모두 딕셔너리로 저장했고 마지막에 스코어만 딕셔너리 안에 있는 리스트에 저장하는 식으로 짯다. 트리 구조로 만들었다고 생각하면 된다.

                                                 CPP
                  backend                                         frontend

     senior                  junior                    senior                  junior  

chick     pizza    chick      pizza        chick     pizza    chick      pizza

[]              []             []        []                []              []             []        []

• 결론적으로 문제의 핵심은 1) 어떤 자료구조에 저장해서 코딩 할 것인가? 2) 효율적인 탐색 알고리즘 정도로 정리할 수 있을 듯 하다.

• l=['cpp','python','java']
  p=['backend','frontend']
  e=['junior','senior']
  f=['pizza','chicken']
  from bisect import bisect_left
  
  def make_dict(lan):
      for i in p:
          lan[i]={}
      for i in p:
          for j in e:
              lan[i][j]={}
      for i in p:
          for j in e:
              for k in f:
                  lan[i][j][k]=[]
      return lan
  
  def sort_score(lan):
  
      for i in p:
          for j in e:
              for k in f:
                  # print(lan[i][j][k])
                  lan[i][j][k] = sorted(lan[i][j][k])
      return lan
  
  def solution(info, query):
      answer = []
      cpp ,python,java ={},{},{}
  
      cpp = make_dict(cpp)
      python=make_dict(python)
      java = make_dict(java)
  
      for i in info:
          lan,pos,exp,food,score = i.split(" ")
          if(lan=='cpp'):
              cpp[pos][exp][food].append(int(score))
          elif(lan=='java'):
              java[pos][exp][food].append(int(score))
          else:
              python[pos][exp][food].append(int(score))
  
      cpp = sort_score(cpp)
      python=sort_score(python)
      java = sort_score(java)
  
      for qu in query:
          #print(i)
          lan,pos,exp,food_score = qu.split(" and")
          food,score = food_score.strip().split(' ')
          lan = [lan.strip()]
          pos = [pos.strip()]
          exp = [exp.strip()]
          food = [food]
          score = int(score)
          if(lan[0]=='-'):
              lan = l
          if(pos[0]=='-'):
              pos =p
          if(exp[0]=='-'):
              exp = e
          if(food[0]=='-'):
              food =f
          cnt=0
          # print('here',lan,pos,exp,food,score)
          for i in lan:
              if(i=='cpp'):
                  cur_lan = cpp
              elif(i=='java'):
                  cur_lan= java
              else:
                  cur_lan = python
              for j in pos:
                  for k in exp:
                      for l1 in food:
                          if(len(cur_lan[j][k][l1])!=0):
                              cnt += len(cur_lan[j][k][l1])-bisect_left(cur_lan[j][k][l1],score)
  
          answer.append(cnt)
          # print(answer)
      return answer