사용 언어: python 3.9.5
❓ Problem
문제 설명
난이도
level 2
🚩 Solution
효율성을 통과하지 못해서 실패함
시도 01)
1. 접근법
하나의 query당 info를 모두 접근한다.
먼저, 마지막 원소인 점수를 검사한 뒤, 점수 조건을 만족하면 문자열이 같은지 검사한다.
2. 코드
def solution(info, query):
answer = []
for q in query:
q = q.split(' and ')
t = q[-1].split(' ')
q[-1] = t[0]
q.append(t[1])
#print(f"q : {q}")
cnt = 0
for i in info:
#print()
i = i.split(' ')
#print(f"i : {i}")
right = True
#print(f"q[4] : {q[4]}")
if int(i[4]) >= int(q[4]):
for j in range(4):
#print(f"pair[0] : {i[j]}")
#print(f"pair[1] : {q[j]}")
if q[j] == '-':
continue
if i[j] != q[j]:
#print("false")
right = False
break
if right:
cnt += 1
#print(f"cnt 1 증가 : cnt = {cnt}")
answer.append(cnt)
#print(f"andswer에 추가 : {answer}")
# #print(answer)
return answer시도 02)
1. 접근법
알고리즘, 시간복잡도 위와 동일함
달라진 점: info를 query의 크기만큼 반복적으로 split(), int() 함수를 호출하던 것을 한 번으로 줄임
query를 split()하는 코드를 replace() 함수를 통해 조금이라도 시간과 메모리를 줄이려고 노력함...
2. 코드
def solution(info, query):
for i in range(len(info)):
info[i] = info[i].split(' ')
info[i][4] = int(info[i][4])
# print(f"info[0] : {info[i]}")
# break
answer = []
for q in query:
q = q.replace(' and ',' ')
q = q.split(' ')
# t = q[-1].split(' ')
# q[-1] = t[0]
# q.append(t[1])
# print(f"q : {q}")
# break
cnt = 0
for i in info:
#print()
# i = i.split(' ')
#print(f"i : {i}")
right = True
#print(f"q[4] : {q[4]}")
if i[4] >= int(q[4]):
for j in range(4):
#print(f"pair[0] : {i[j]}")
#print(f"pair[1] : {q[j]}")
if q[j] == '-':
continue
if i[j] != q[j]:
#print("false")
right = False
break
if right:
cnt += 1
#print(f"cnt 1 증가 : cnt = {cnt}")
answer.append(cnt)
#print(f"andswer에 추가 : {answer}")
# #print(answer)
return answer시도 03)
1. 접근법
"정렬"
info를 매 query마다 모두 돌아서 비효율적이라는 생각이 든다.
그래서 info를 도는 시간을 줄이기 위해 혹시나 info를 먼저 정렬해야하나 싶은 생각이 들었다.
하지만 정렬을 어떻게 해도 모든 info를 검사한다면 시간복잡도는 크게 달라지지 않을 거라 효율성 테스트를 통과하지 못할 것 같다.
그런데 시간이 너무 지체되어 정렬을 한다면 어떻게 풀건지 아이디어만 조금 생각해보고 정답을 보기로 했다.
query의 요구 조건인 언어, 직군, 경력, 소울 푸드, 점수 중에 무엇을 기준으로 info를 정렬하면 좋을까? query에서 많이 등장하는 조건을 정렬의 기준으로 삼는게 더 효율적일 것이다. 그런데 이 중에서 점수 이외의 조건들은 '-'일 수도 있으므로 점수 외에는 무엇이 빈도가 높을지 query를 모두 들여다보기 전까지 알 수 없다. 따라서 점수를 기준으로 info를 정렬하면 좋을 거라고 생각하였다.
-
정답
참고: https://velog.io/@study-dev347/프로그래머스-순위-검색
mport bisect changes = [] tmp = [] # 16가지의 경우의 수를 만들어주는 함수 def make_cases(): global changes, tmp if len(tmp) == 4: t = [] for index in tmp: t.append(index) changes.append(t) return for i in (False, True): tmp.append(i) make_cases() tmp.pop() # True를 가리키는 인덱스에 해당하는 속성 값을 '-'으로 바꿔준다. def replace(change, data): for i in range(4): if change[i]: data[i] = '-' return data def copy(data): _data = [] for item in data: _data.append(item) return _data def search(scores, num): size = len(scores) return size - bisect.bisect_left(scores, num, lo=0, hi=size) def solution(info, query): global changes answer = [] info_dict = {} make_cases() # query를 위한 info 전처리 for data in info: data = data.split() score = int(data[-1]) data = data[:4] for change in changes: _data = copy(data) _data = replace(change, _data) _data = ''.join(_data) if _data not in info_dict.keys(): info_dict[_data] = [score] else: info_dict[_data].append(score) # info_dict[key] 정렬 for key in info_dict.keys(): info_dict[key].sort() for q in query: q = q.split() score = int(q[-1]) _q = '' # query 문자열 처리 for item in q[:len(q)-1]: if item != 'and': _q += item # 문의 조건을 만족하는 지원서들의 수 찾기 if _q not in info_dict.keys(): answer.append(0) else: cnt = search(info_dict[_q], score) answer.append(cnt) return answer
3. 시간복잡도
4. 결과
실패
원인:
시간 초과
5. 소요 시간
45분
📕 피드백
1. 검색한 내용
-
split('') : 괄호 안에 문자열을 쪼갤 기준 넣기, 반환타입은 리스트
ex) 공백 기준으로 문자열을 자르고 싶으면
str = str.split(' ') -
replace('a','b') : 문자열에서 첫번째 인자 'a' 를 두번째 인자 'b'로 바꿈
ex)
str = str.replace('a', 'b')
2. 실수
제출할 때 print 함수 안지우고 냄
3. 발전 방향 (개선/추가사항)
4. 다른 사람 풀이
풀이1)
- 링크
https://velog.io/@djagmlrhks3/Algorithm-Programmers-순위-검색-by-Python
- 접근법
- 코드
from bisect import bisect_left
from itertools import combinations
def make_all_cases(temp):
cases = []
for k in range(5):
for li in combinations([0, 1, 2, 3], k):
case = ''
for idx in range(4):
if idx not in li:
case += temp[idx]
else:
case += '-'
cases.append(case)
return cases
def solution(info, query):
answer = []
all_people = {}
for i in info:
seperate_info = i.split()
cases = make_all_cases(i.split())
for case in cases:
if case not in all_people.keys(): all_people[case] = [int(seperate_info[4])]
else: all_people[case].append(int(seperate_info[4]))
for key in all_people.keys():
all_people[key].sort()
for q in query:
seperate_q = q.split()
target = seperate_q[0] + seperate_q[2] + seperate_q[4] + seperate_q[6]
if target in all_people.keys():
answer.append(len(all_people[target]) - bisect_left(all_people[target], int(seperate_q[7]), lo=0, hi=len(all_people[target])))
else:
answer.append(0)
return answer- 배울 점
시간복잡도는 알고리즘을 바꿔야지 자잘한 함수 호출로 변화시키지 못한다.
그룹으로 분류할 때 딕셔너리 자료형을 사용해보자
