문제
| 지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
시도
방법1. 문자들을 다 숫자 코드로 바꿔서 일치하는 거 찾으려고 했음
- 결과
답은 맞으나,, 효율성에서 실패.
딕셔너리 썼는데,각 utils를 고유값으로 해서 그런가봐 ㅍㅅㅍ((문풀후 추가 : 딕셔너리까진 맞음, 치환도 괜찮을듯, 다만 점수 찾는 부분이 시간 오래걸리는 원인이었음))
# '''
# 조건에 맞는 지원자는 몇 명? => 탐색?
# 언어 : cpp java python
# 직군 : back front
# 경력 : junior senior
# 음식 : chicken pizza
# userIdx = [0,1,2,3,,,, ]
# lang_lst = [1, 1, 0, 2,, ]
# front_lst = [0,1,0]
# senior_lst = [1,0,1,0,,,]
# food_lst = [0, 1]
# '''
utils = {
"cpp":'0',
"java":'1',
"python":'2',
"backend":'3',
"frontend":'4',
"junior":'5',
"senior":'6',
"chicken":'7',
"pizza":'8',
"-": '9'
}
def calculate(dic, code, score):
if dic.get(code):
cnt = len(list(filter(lambda x : int(x) >= int(score), dic[code])))
return cnt
else:
# print("any result in user")
return 0
def solution(info, query):
answer = []
users_dic = {}
result = []
for u in info:
code = ''
for e in u.split():
if utils.get(e):
code+=utils[e]
else:
if not users_dic.get(code):
users_dic[code] = [e]
else:
users_dic[code].append(e)
code = ''
# print(users_dic)
q_code_list = [[utils[code] if utils.get(code) else str(code) for code in q.replace('and','').split()] for q in query]
# print(q_code_list)
for q_code in q_code_list: # '1359'
# 012. 34. 56. 78
if not '9' in q_code[:4]:
result.append(calculate(users_dic, ''.join(q_code[:4]), q_code[4]))
else:
temp_tot = 0
temp = [''] # '1','2'
for idx in range(4): # '9999'
if q_code[idx]=='9' and idx == 0:
temp = [t+str(e) for t in temp for e in range(0,3)]
if q_code[idx]=='9' and idx == 1:
temp = [t+str(e) for t in temp for e in range(3,5)]
if q_code[idx]=='9' and idx == 2:
temp = [t+str(e) for t in temp for e in range(5,7)]
if q_code[idx]=='9' and idx == 3:
temp = [t+str(e) for t in temp for e in range(7,9)]
if q_code[idx] != '9':
temp = [t+str(q_code[idx]) for t in temp]
for case_code in temp:
temp_tot += calculate(users_dic, case_code, q_code[4]) # q_code[4] 점수
result.append(temp_tot)
return result
방법2: 이진탐색 추가
(...상단 생략...)
for q in query:
q = [x for x in q.split() if (x!='and' and x!='-')]
q_key = ''.join(q[:-1])
q_score = int(q[-1])
cnt = 0
if dic.get(q_key):
v_sorted = dic[q_key]
if len(dic[q_key]) == 1 :
cnt = 1 if dic[q_key][0] >= q_score else 0
elif v_sorted[-1] < q_score:
cnt = 0
else:
s = 0
e = len(v_sorted)-1
while s<=e:
mid = (s+e)//2
if v_sorted[mid] >= q_score: # go to smaller
e = mid-1
cnt = v_sorted[mid:]
if v_sorted[mid] < q_score: # go to bigger
s = mid+1
answer.append(cnt)=> 속도가 빨라졌지만, 아직 통과 못함
카카오 해설
본 문제는 정확성 테스트와 효율성 테스트 두 가지 방식으로 검증하는 문제입니다. 효율성 테스트의 경우 주어진 시간 내에 실행이 완료되어야 하므로, 최적화된 구현 방법을 고민할 필요가 있습니다.
우선, 매 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있습니다.
그러나 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없습니다. 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.
예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.
언어 직군 경력 소울 푸드 점수
java backend junior pizza 150
– backend junior pizza 150
java – junior pizza 150
java backend – pizza 150
java backend junior – 150
– – junior pizza 150
– backend – pizza 150
… (생략)
java – – – 150
– – – – 150
검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.
따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다. 이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.
이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.
최종 풀이
: 이진탐색 + cnt 개선한 풀이
from itertools import combinations
def solution(info, query):
answer = []
dic = {}
for person in info:
content_key = person.split()
score = int(content_key[-1])
for i in range(5):
comb =list(combinations(content_key[:4], i))
for c in comb:
c = ''.join(c)
if dic.get(c):
dic[c].append(score)
else:
dic[c] = [score]
# dic = {k:sorted(v) for k, v in dic.items()}
for k in dic.values():
k.sort()
for q in query:
q = [x for x in q.split() if (x!='and' and x!='-')]
q_key = ''.join(q[:-1])
q_score = int(q[-1])
cnt = 0
if dic.get(q_key):
v_sorted = dic[q_key]
if len(dic[q_key]) == 1 :
cnt = 1 if dic[q_key][0] >= q_score else 0
elif v_sorted[-1] < q_score:
cnt = 0
else:
s = 0
e = len(v_sorted)-1
while s<=e:
mid = (s+e)//2
if v_sorted[mid] >= q_score: # go to smaller
e = mid-1
if v_sorted[mid] < q_score: # go to bigger
s = mid+1
cnt = len(v_sorted)-s
answer.append(cnt)
return answer- 교훈
- [ 효율성 ] 값에 들어있는 리스트 탐색할 때, 하나씩 담는 것보다 sorting해주고 이진탐색으로 하는 게 훨씬 빠르다.
- [ 효율성 ] len(v_sorted[mid:]) 를 while 안에 넣어서 매번 cnt를 계산할 때는 통과 못 했는데, while 밖으로 빼니까 통과 했다
- [ 표현식 ] 딕셔너리의 값에 리스트가 들어가는 경우, `for k in dic.values(): k.sort()` 로 간단하게 sorting 할 수 있다.
- 가장 어려웠던 부분
- 답을 봐도 '-' 를 처리하는 부분이 이해가 안 갔었다. 나는 들어온 info를 하나씩 놓는 걸 기준으로
그 외 알게된 것들
- dictionary.get(key) : 딕셔너리에 해당 키가 존재하는지 확인하는 메서드
dic = {'kim':0, 'lee':0}
if dic.get('kang'):
print('it has kang')
else:
print('it has'nt kang')
(22.09.14 utils 추가 시도)
utils 에 넣고 코드를 키로 만들어서 풀이해봄
1차 시도 : utils 생성, 이진탐색 함수 분리
1차 결과 : 한 두건 빼고 메모리는 비슷하고, 속도가 2배 늘어남. 숫자 코드여도 '147' 문자형으로 키값을 처리하기 때문인 듯.
➪ 결론 : utils 숫자 값을 가지러 utils dictionary에 접근하는 과정이 추가되기 때문에, 오히려 느려졌다.
2차 시도 : 그렇다면 dictionary의 키를 숫자로 변환하면?, code가 '' 빈 문자열이었으면, 0으로 변환
2차 결과 : 메모리 역시 비슷하고, 속도는 위에 보다 조금 더 느려짐. 널체크 후 변환 때문인 거 같다..!
➪ 결론 : 딕셔너리의 키가 숫자형인지 문자형인지는 속도에 유의미한 차이를 가져오지 않는다.
- 1차 시도 코드
utils =
{0: 0, 'cpp': 1, 'java': 2, 'python': 3, 'backend': 4,
'frontend': 5, 'junior': 6, 'senior': 7, 'chicken': 8, 'pizza': 9}
from itertools import combinations
# from bisect import bisectleft
a = ['cpp', 'java', 'python']
b = ['backend', 'frontend']
c = ['junior', 'senior']
d = ['chicken', 'pizza']
# 리스트 탐색 => binary
def getCnt(users, scoreCut):
userLong = len(users)
if userLong == 0:
return 0
if userLong == 1 :
if int(users[0]) < scoreCut:
return 0
else:
return 1
s = 0
e = userLong-1
while s <= e:
mid = (s+e)//2
userScore = users[mid]
if userScore < scoreCut:
s = mid + 1
if userScore >= scoreCut:
e = mid - 1
return userLong-s
def solution(info, query):
utils = {name: id for id, name in enumerate([0]+a+b+c+d)}
scoreTable = {}
for user in info:
row_user = user.split()
# (a,b,c,d)
# (_,b,c,d)
# (a,_,c,d)
# ...
# (a,b,c,_)
# (_,_,_,_)
content, userScore = row_user[:4], int(row_user[-1])
for long in range(5):
keylist = list(combinations(content, long))
# scoreTable = {''.join([str(utils[name]) for name in k]):[userScore] for k in keylist} # {코드 : 점수, 코드 : 점수}
for i in keylist:
keyCode = ''.join([str(utils[name]) for name in i])
if scoreTable.get(keyCode):
scoreTable[keyCode].append(userScore)
else:
scoreTable[keyCode] = [userScore]
for k in scoreTable.keys():
scoreTable[k].sort()
# query
ans = []
for q in query:
row_query = q.replace('and','').split()
# conditions, standScore = row_user[:-2], row_user[-1]
conditions = [e for e in q.split() if e != 'and' and e !='-']
qCode = ''.join([str(utils[name]) for name in conditions[:-1]])
# qCode = ''.join(str(utils[name]) for name in )
standScore = int(conditions[-1])
cnt = 0
if scoreTable.get(qCode):
cnt = getCnt(scoreTable[qCode], standScore)
ans.append(cnt)
return ans
* 그외 시도
utils 를 리스트에서 생성하는 거 말고, 미리 만들어두고 해봄 => 차이 없음
함수 분리한 거 다시 내부로 넣고 돌리면 메모리 줄어드나..?
참고 블로그
https://dev-note-97.tistory.com/131
https://firsteast.tistory.com/103
https://hongcoding.tistory.com/56
'⚡️algorithm > step-up ++' 카테고리의 다른 글
| [스택, 수 비교] 프로그래머스 lv2. 뒤에 있는 큰 수 찾기 (0) | 2023.02.23 |
|---|---|
| [다익스트라, Dijkstra, 구조] 백준 1753. 최단 경로 (0) | 2022.10.12 |
| [DP, 2차원, 누적합, 파이썬] 백준 11660. 구간합구하기 (1) | 2022.10.03 |
| [Dictionary 탐색] 프로그래머스 lv2. 신고결과받기 (feat. enumerate, set, dictionary) (0) | 2022.09.08 |