코딩 테스트/Level 4
무지의 먹방 라이브
컴닥
2020. 10. 18. 10:25
반응형
무지의 먹방 라이브
2019 KAKAO BLIND RECRUITMENT
1230명 완료
풀어보니 특별히 족보있는 알고리듬이 필요한 건 아니었고.
왕창 왕창 한꺼번에 처리해 주면 통과할 수 있었습니다.
Level 3에 있어도 될 법한 문제
https://programmers.co.kr/learn/courses/30/lessons/42891
코딩테스트 연습 - 무지의 먹방 라이브
programmers.co.kr
시간제한을 못 넘기겠지만 이해한 것이 맞는지 확인해 봅니다.
다행히 잘 맞습니다.
def solution(food_times, k):
answer = time = food_num = 0
while time <= k:
if sum(food_times) == 0:
return -1
if food_times[food_num] > 0:
food_times[food_num] -= 1
print(f"{time}~{time + 1}초 동안 {food_num + 1}번 음식을 섭취한다 남은 시간은 {food_times}이다.")
answer = food_num + 1
time += 1
food_num = (food_num + 1) % len(food_times)
return answer0~1초 동안 1번 음식을 섭취한다 남은 시간은 [2, 1, 2]이다.
1~2초 동안 2번 음식을 섭취한다 남은 시간은 [2, 0, 2]이다.
2~3초 동안 3번 음식을 섭취한다 남은 시간은 [2, 0, 1]이다.
3~4초 동안 1번 음식을 섭취한다 남은 시간은 [1, 0, 1]이다.
4~5초 동안 3번 음식을 섭취한다 남은 시간은 [1, 0, 0]이다.
5~6초 동안 1번 음식을 섭취한다 남은 시간은 [0, 0, 0]이다.정확성 테스트
테스트 27 〉 통과 (3490.55ms, 10.9MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)왕창 왕창 지우면 빠를 것 같습니다.
왕창 왕창 지울 수 없는 부분까지 가면
위 코드를 이용해 1씩 지웁니다.
하지만 실패.
1/10 수준으로 시간을 줄였는데도 실패라니.스케치 수준이라 코드가 조잡합니다.
아무 생각 없이 딕셔너리를 썼던 것도 그닥...
튜플과 힙큐보다 빨랐던 건 함정..
def solution(food_times, k):
answer = time = 0
# prev_time = 0
food_times = {i + 1: v for i, v in enumerate(food_times)}
min_time = min(food_times.values())
while k >= min_time * len(food_times) + time:
# prev_time = time
time += min_time * len(food_times)
for key in tuple(food_times):
food_times[key] -= min_time
if food_times[key] == 0:
del food_times[key]
# print(f"{prev_time} ~ {time}초 동안 각 {min_time}개의 음식을 섭취한다. 남은 시간은 {food_times}이다")
if not food_times:
return -1
min_time = min(food_times.values())
while k >= time:
for key in tuple(food_times):
if time == k:
return key
answer = key
# prev_time = time
time += 1
food_times[key] -= 1
if food_times[key] == 0:
del food_times[key]
# print(f"{prev_time} ~ {time}초 동안 {key}번 음식을 섭취한다. 남은 시간은 {food_times}이다.")
if not food_times:
return -1
return answer
파이썬 3.8부터 도입된 Assignment Expression을 쓰면 2줄은 더 줄일 수 있습니다.
심지어 보기도 깔끔합니다.... while문으로 for문 비슷하게 쓸 수도 있고.. 전 극호네요..
귀도형... 형이 옳았어...
https://www.python.org/dev/peps/pep-0572/
http://www.ciokorea.com/news/39153
def solution(food_times, k):
answer = time = 0
# prev_time = 0
food_times = {i + 1: v for i, v in enumerate(food_times)}
while k >= (min_time := min(food_times.values())) * len(food_times) + time:
# prev_time = time
time += min_time * len(food_times)
for key in tuple(food_times):
food_times[key] -= min_time
if food_times[key] == 0:
del food_times[key]
# print(f"{prev_time} ~ {time}초 동안 각 {min_time}개의 음식을 섭취한다. 남은 시간은 {food_times}이다")
if not food_times:
return -1
while k >= time:
for key in tuple(food_times):
if time == k:
return key
answer = key
# prev_time = time
time += 1
food_times[key] -= 1
if food_times[key] == 0:
del food_times[key]
# print(f"{prev_time} ~ {time}초 동안 {key}번 음식을 섭취한다. 남은 시간은 {food_times}이다.")
if not food_times:
return -1
return answer정확성 테스트
테스트 27 〉 통과 (29.34ms, 11.1MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)생각해보니
모든 딕셔너리(또는 배열의) 시간 값을 변경하는데
시간이 많이 걸리는 것 같습니다.
각 배열의 시간값을 변경하지 말고..
대신 경과 시간 변수를 만들어서 사용해야겠습니다.
변수 하나만 수정하면 되니까요..
계속 최소값을 찾는 것 보단 sort 한번 하는 게 빠르겠고..
마지막에도 sort를 한번 해줘야 하니..
딕셔너리보다는 튜플를 쓰는 것이 편했습니다.
딕셔너리는 파이썬 3.6부터 비공식적으로,
3.7부터는 공식적으로 '순서'가 있습니다만.
소트가 바로 되지도 않고, 인덱스도 없고...
딕셔너리 관련 라이브러리 중에 뭔가 있을 것 같지만....
def solution(food_times, k):
from collections import deque
time = min_time = 0
food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
while food_times:
if k == time:
return sorted(food_times, key=lambda a: a[1])[0][1]
if k >= time + (food_times[0][0] - min_time) * len(food_times):
time += (food_times[0][0] - min_time) * len(food_times)
min_time = food_times[0][0]
elif k >= time + 1 * len(food_times): # 이 부분의 1을 키우는 게 해결책..
time += 1 * len(food_times) #
min_time += 1 #
else:
return sorted(food_times, key=lambda a: a[1])[k - time][1]
while food_times and food_times[0][0] == min_time:
food_times.popleft()
# print(f" ~ {time}초 동안 음식을 섭취한다. 남은 시간은 {food_times}이다")
return -1정확성 테스트
테스트 27 〉 통과 (1.33ms, 11MB)
효율성 테스트
테스트 1 〉 통과 (275.87ms, 160MB)
테스트 2 〉 실패 (시간 초과)거의 구현을 했고..
효율성 2번 테스트에서 걸리는데..
[1,1,100000000000000000000000] 이런 식의 테스트 코드일 것 같네요..
중간에 하나씩 올리는 과정을 왕창 왕창으로 바꿔주면 될 것 같습니다.
드디어 해결...
def solution(food_times, k):
from collections import deque
time = min_time = 0
food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
while k != time:
if k >= time + (food_times[0][0] - min_time) * len(food_times):
time += (food_times[0][0] - min_time) * len(food_times)
min_time = food_times[0][0]
elif (k - time) // len(food_times) > 0:
time += (k - time) // len(food_times) * len(food_times)
min_time += (k - time) // len(food_times)
else:
return sorted(food_times, key=lambda a: a[1])[k - time][1]
while food_times[0][0] == min_time:
food_times.popleft()
if not food_times:
return -1
return sorted(food_times, key=lambda a: a[1])[0][1]테스트 1 〉 통과 (341.63ms, 40.5MB)
테스트 2 〉 통과 (78.22ms, 40.2MB)
테스트 3 〉 통과 (325.88ms, 40.1MB)
테스트 4 〉 통과 (318.22ms, 40.3MB)
테스트 5 〉 통과 (343.91ms, 40.4MB)
테스트 6 〉 통과 (298.60ms, 40.7MB)
테스트 7 〉 통과 (331.06ms, 40.2MB)
테스트 8 〉 통과 (346.07ms, 41.3MB)Assignment Expression
def solution(food_times, k):
from collections import deque
time = min_time = 0
food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
while k != time:
if k >= time + (time_stack := (food_times[0][0] - min_time) * len(food_times)):
time += time_stack
min_time = food_times[0][0]
elif (quotient := (k - time) // len(food_times)) > 0:
time += quotient * len(food_times)
min_time += quotient
else:
return sorted(food_times, key=lambda a: a[1])[k - time][1]
while food_times[0][0] == min_time:
food_times.popleft()
if not food_times:
return -1
return sorted(food_times, key=lambda a: a[1])[0][1]테스트 1 〉 통과 (284.39ms, 40.4MB)
테스트 2 〉 통과 (79.28ms, 40.3MB)
테스트 3 〉 통과 (318.55ms, 40.3MB)
테스트 4 〉 통과 (306.55ms, 40.2MB)
테스트 5 〉 통과 (308.27ms, 40.5MB)
테스트 6 〉 통과 (336.53ms, 40.8MB)
테스트 7 〉 통과 (349.50ms, 40.2MB)
테스트 8 〉 통과 (296.78ms, 41.2MB)디큐를 안써도 되죠?
def solution(food_times, k):
time = min_time = 0
food_times = sorted([(v, i + 1) for i, v in enumerate(food_times)], key=lambda x: -x[0])
while k != time:
if k >= time + (time_stack := (food_times[-1][0] - min_time) * len(food_times)):
time += time_stack
min_time = food_times[-1][0]
elif (quotient := (k - time) // len(food_times)) > 0:
time += quotient * len(food_times)
min_time += quotient
else:
return sorted(food_times, key=lambda a: a[1])[k - time][1]
while food_times[-1][0] == min_time:
food_times.pop()
if not food_times:
return -1
return sorted(food_times, key=lambda a: a[1])[0][1]테스트 1 〉 통과 (289.83ms, 49.6MB)
테스트 2 〉 통과 (91.36ms, 48MB)
테스트 3 〉 통과 (272.23ms, 49.5MB)
테스트 4 〉 통과 (197.92ms, 49.6MB)
테스트 5 〉 통과 (265.98ms, 49.6MB)
테스트 6 〉 통과 (282.85ms, 49.6MB)
테스트 7 〉 통과 (244.34ms, 49.6MB)
테스트 8 〉 통과 (279.32ms, 49.7MB)디큐가 더 빠르군요.. --;
반응형