2019 kakao blind recruitment
문제 링크 :
https://programmers.co.kr/learn/courses/30/lessons/42891
내가 생각한 문제 풀이
[시도1]
효율성 테스트가 있는 문제였고, 시나리오대로 진행해서는 효율성 테스트를 통과할 수 없다고 판단하여 다른 방법을 생각했다.
1) 우선 음식 시간을 sort하고 set하여 중복 없이 정렬한다.
2) length 변수(먹어야 하는 음식의 개수)를 len(food_times)로 설정한다.
3) sort된 음식 시간을 반복문으로 돌면서, k보다 음식 시간 길이가 작은 경우 huddle(카운트 되는 시간의 하한선)을 새로 설정하고, k에서 음식 시간을 뺸다.
4) k보다 음식 시간 길이가 큰 경우 첫 번째부터 돌면서 huddle을 넘는 것들을 카운트한다. 이 때 리스트는 0부터 시작하므로 return시 index보다 1 큰 수를 리턴하며, k가 len(food_times)인 경우 0번째부터 다시 리턴할 수 있는 수를 확인한다.
[시도2]
그냥 정확도를 맞추고자 했다.
반복문 안에 for문을 넣어서 첫번째 음식부터 돌면서 확인하도록 했고, k가 -1인 경우(방송 재개 되면 먹어야 할 음식) set(food_times)인 경우(k는 남았는데 음식을 다 먹은 경우) 나머지 중에서 음식을 먹은 시간이 아직 남은 경우로 나누었다.
def solution(food_times, k):
while True:
for i in range(len(food_times)):
if k == -1: # 만약에 i가 마지막 번째인 경우
return i
if set(food_times) == {0}: #k가 0이 아닌데 음식을 다 먹은 경우
return -1
if food_times[i] > 0:
food_times[i] -= 1
k -= 1시간 / 결과 / 패착
[시도1]
소요 시간 : ??
결과(정확도) : 정확도 하나 맞음
패착 :
전체적으로 그냥 문제가 있는 코드인 것 같다 어느 하나의 해결로는 해결될 것 같지 않은.. 답을 보기 전에 정확성 테스트는 다 맞춰야겠다는 생각이 들어서 다시 코드를 작성했다.
카카오 해설(https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/)을 보니 이 아이디어 자체는 맞는 것으로 생각된다(최소 시간 * 한번에 삭제할 수 있는 음식 리스트)를 한 번에 삭제하는 아이디어
[시도2]
소요 시간 : 10분
결과(정확도) : 5개 틀림
패착 :
왜 정확도가 다 맞지 않는지 이해가 가지 않는다. 검색을 해봐야 할 듯
완전탐색에서 어떤 문제 때문에 걸리는지 완전 모르겠다. 우선 정답에 대해서 알아봐야 할 것 같다.
문제 해설
[힙 사용]
1)heap을 만들어서 각 (음식을 먹는데 걸리는 시간, index)를 삽입한다.
이 때 index+1을 삽입하면 문제와 조건(1부터 시작)을 맞추기 쉽다
2)반복문에서 (가장 적게 걸리는 시간 - 이전에 제거된 시간) * 남은 음식 시간을 계산한다
3)k보다 계산한 결과가 크거나 같다면 heap에서 그 값을 빼고 변수들을 갱신한다.
같은 경우는 포함해주어야 한다. 만약 음식과 k가 똑떨어진다면 -1을 리턴해야 하기 때문이다.
4)k보다 계산값이 작다면 남은 음식을 sort해서 해당 idx값을 리턴한다.
heap에서 음식이 빠져 나가기 때문에 이게 제외되는 음식인지 하나하나 고려할 필요가 없다는 점이 인상적이었다.
[이분 탐색 사용]
몇 바퀴를 한 번에 빼준 뒤에 추가적인 탐색을 진행할 것인가 라는 아이디어에서 시작한다.
한 번에 빼줄 바퀴 값을 이분 탐색으로 구한다.
어떻게 구하냐면,
mid가 한 번에 빼줄 값이 되고, 이분 탐색을 진행할 때마다 각 food time에서 mid값을 빼서 음수가 되는 경우 그 수만큼 초수에서 제거해 준다.
그래서 최종으로 빼지는 값이 정해지고, 리스트(foodtimes)에서 빼 준뒤 거기서부터 카운트 하면 된다.
[우선순위 큐 사용]
heap이 우선순위를 구현한 것이기 때문에 알고리즘 상 동일
코드
힙 사용 코드
import heapq
def solution(food_times, k):
answer = -1 # default
h = []
n = len(food_times)
p = 0
for i in range(n):
heapq.heappush(h, (food_times[i], i+1)) #이떄 i가 아닌 i+1부터 삽입하면 문제 조건에 맞출 수 있다
while h:
t = (h[0][0] - p) * n # 이때 힙에서 뽑지 말고 값만 조회한다. 확실히 뺴도 되는 상황인지 확인해야 하기 때문
if k >= t:
k -= t
n -= 1
p, _ = heapq.heappop(h)
else:
sortfood = sorted(h, key=lambda x:x[1]) # sort 할때 lambda 사용하면 key=lamdba x=x[1]
idx = k % n
answer = sortfood[idx][1]
break
return answer
추가 공부
priority queue와 heap의 관계
python에서 priorityqueue 모듈이 heapq 모듈을 통해 구현되어 있다.
que = PriorityQueue()
# 원소 추가
que.put(4)
# 원소 삭제
temp = que.get()tip for me
1부터 시작하는 경우 idx조절을 하는 스킬
lambda 사용법을 아직도 ;; 잘 모른다
h.sort(key=lambda x:x[1])key 를 꼭 써주자
의외로 한번에 음식을 빼주는 아이디어 자체는 맞았는데 문제를 풀지 못한 이유는
1) 구현 미흡 : heap을 사용할 생각을 전혀 하지 못했다.
개선 : heap queue stack등을 한 번 더 생각해보기
2) 코너케이스
너무 세분화하려는 문제와 몇 가지 조건을 전혀 고려하지 않는 문제 동시에 발생
나의 알고리즘에 자신감을 가지고 그걸 완벽하게 구현해보자
