ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 무지의 먹방 라이브
    코딩 테스트/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 answer
    0~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)

    디큐가 더 빠르군요.. --;

    반응형
Designed by Tistory.