programmers.co.kr/learn/courses/30/lessons/72412
문제 설명
문제에 대한 설명이 굉장히 길어 링크로 대체합니다.
간단히 설명하자면, info에 있는 목록 중 query에 있는 목록을 만족하는 개수를 구하는 문제입니다.
풀이 과정
처음에는 딕셔너리와 이분탐색을 이용하지 않고, 주어진 리스트를 그대로 이용해
각 리스트 요소마다 하나씩 매번 검사하는 방법을 이용했습니다.
정확성은 통과를 했지만, 역시 효율성에서 실패했습니다.
방법 1
정확성 성공
효율성 실패
from itertools import combinations
def solution(info, query):
answer = [0 for i in range(len(query))]
infol = []
queryl = []
for i in range(len(info)):
infol.append(info[i].split())
# tmp = ['java', 'backend', 'junior', 'pizza', '150']
for j in range(len(query)):
queryl.append(query[j].split())
while len(queryl[j]) > 5:
queryl[j].remove("and")
for i in range(len(infol)):
for j in range(len(queryl)):
flag = 0
for k in range(4):
if infol[i][k] != queryl[j][k]:
if queryl[j][k] != '-':
flag = 1
break
if flag == 0:
if int(infol[i][4]) >= int(queryl[j][4]):
answer[j] += 1
return answer
효율성을 통과하기 위해 사용한 방법은,
딕셔너리(자바의 hash와 비슷한 파이썬의 자료구조), 이분탐색(BinarySearch)를 이용했습니다.
과정은 다음과 같습니다.
① info 안의 문자열을 공백을 기준으로 분리합니다. ( ex ['java', 'backend', 'junior', 'pizza', '150'] )
② 분리한 것 중, 앞의 4부분(java,backend..)을 키값으로, 마지막부분(150)을 value값으로 분리 합니다.
③ 키값들로 만들 수 있는 모든 조합을 생성합니다. (combinations 이용)
④ 이 조합으로 딕셔너리를 생성합니다. 해당 키값이 딕셔너리에 이미 존재하면 value값을 그 키의 value값에 추가합니다. { 'javabackendjuniorpizza' : [150...] , 'java' : [100...] , ... } 식으로 생성이 되겠죠?
⑤ 딕셔너리의 각 원소마다 value값들을 기준으로 정렬합니다. [100,150,200...]식으로 되도록
⑥ query도 마찬가지로 분리합니다. ( query에는 and와 -도 있기 때문에 제거를 하여 info와 같은 형식으로 만듭니다. )
⑦ 이제 query를 한바퀴 돌면서, info딕셔너리를 탐방하게 되는데,
query의 key값이 info딕셔너리의 키값으로 존재하면 그 info딕셔너리의 value값들을 가져옵니다.
⑧ 가져온 점수값에서 기준 점수값을 넘는 것들의 개수를 이분탐색을 통해 구하면 됩니다.
방법 2
정확성 성공
효율성 성공
from itertools import combinations
from bisect import bisect_left
def solution(info, query):
answer = []
info_dict = {}
for i in range(len(info)):
infol = info[i].split() # info안의 문자열을 공백을 기준으로 분리
mykey = infol[:-1] # info의 점수제외부분을 key로 분류
myval = infol[-1] # info의 점수부분을 value로 분류
for j in range(5): # key들로 만들 수 있는 모든 조합 생성
for c in combinations(mykey, j):
tmp = ''.join(c)
if tmp in info_dict:
info_dict[tmp].append(int(myval)) # 그 조합의 key값에 점수 추가
else:
info_dict[tmp] = [int(myval)]
for k in info_dict:
info_dict[k].sort() # dict안의 조합들을 점수순으로 정렬
for qu in query: # query도 마찬가지로 key와 value로 분리
myqu = qu.split(' ')
qu_key = myqu[:-1]
qu_val = myqu[-1]
while 'and' in qu_key: # and 제거
qu_key.remove('and')
while '-' in qu_key: # - 제거
qu_key.remove('-')
qu_key = ''.join(qu_key) # dict의 key처럼 문자열로 변경
if qu_key in info_dict: # query의 key가 info_dict의 key로 존재하면
scores = info_dict[qu_key]
if scores: # score리스트에 값이 존재하면
enter = bisect_left(scores, int(qu_val))
answer.append(len(scores) - enter)
else:
answer.append(0)
return answer
전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
'Algorithm > Binary Search' 카테고리의 다른 글
[백준] 12015번 가장 긴 증가하는 부분 수열 2 (Python 파이썬) (0) | 2021.04.04 |
---|---|
[백준] 1300번 K번째 수 (Python 파이썬) (0) | 2021.04.04 |
[백준] 10816번 숫자 카드 2 (Python 파이썬) (0) | 2021.04.02 |
[백준] 1654번 랜선 자르기 (Python 파이썬) (0) | 2021.01.27 |
[백준] 3020번 개똥벌레 (Python 파이썬) (0) | 2021.01.25 |