[python] 무지의 먹방 라이브-2019 KAKAO BLIND RECRUITMENT

SJ H·2022년 5월 30일
0

문제-무지의 먹방 라이브

https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3

문제 설명

2019 KAKAO BLIND RECRUITMENT에서 출제되었던 문제입니다. 자세한 건 링크에서 확인해주시면 되겠습니다!

🤨풀이를 어떻게 생각했는가?

1. 문제의 조건

  • k초 후에 먹어야 할지를 출력. 없을 경우 -1.
  • 이 때, 총 음식시간이 k보다 작으면 -1 -> 첫 종료조건
  • 순서대로 음식을 섭취해야 한다. 마지막 순서까지 갔다면, 다시 처음 음식을 섭취한다.
  • 다음 음식을 다 먹은 상태라면, 그 다음 음식을 섭취한다. ex) 1->2->3일 경우, 2를 모두 섭취했다면 3의 음식을 먹는다.

2. 고민 과정

  • 단순 반복해서 확인 시, 오랜 시간이 소요 된다. -> 조건 중 k,food_times의 최댓값만 봐도 알 수 있다.
  • 이 때 단순 구현이 아니라고 판단하여 시뮬레이션 해보기로 했다. (하기 참조)

    먹는 시간은 [2,4,3,1,5,8,6] k는 28초로 정한다.
    한바퀴씩 돌려서, 마지막에 남는 음식이 뭔지 계산해본다.
    리스트, 한 바퀴에 걸린시간, 총 남은 시간 순이다.
    [2,4,3,1,5,8,6] 0초, 28초
    [1,3,2,0,4,7,5] 7초 ,21초
    [0,2,1,0,3,6,4] 6초, 15초
    [0,1,0,0,2,5,3] 5초, 10초
    [0,0,0,0,1,4,2] 4초, 6초
    [0,0,0,0,0,3,1] 3초, 3초
    [0,0,0,0,0,2,0] 2초, 1초
    [0,0,0,0,0,1,0] 1초, 0초

😮새롭게 알게된 것

  • 하나가 없어지면 전체를 한번 도는데 1초씩 단축된다. 그렇다면 뭐를 먼저 다 먹는지 체크 한 후, 초에서 전체 인덱스 개수만큼 빼주면 어떨까??

  • 가령 4번 음식이 1이므로, 1바퀴를 돌면 다 먹게된다. 일반 1바퀴를 빼고, k-7 = 21초
    이제는 총 인덱스가 6개다. 여기서 최소를 구하면 또 1개이므로 21-6 = 15초
    5개, 또 1개가 최소다. 15-5 = 10초
    4개, 또 1개다...리스트를 잘못 잡았나??...10-4=6초
    3개, 최소는 1, 6-3 = 3초
    2개, 최소 1, 3-2 = 1초

  • 마지막이 2이므로 2바퀴 돌아야하는데, k가 1밖에 남지 않았다.

  • 최종적으로 k는 0이 되었다. 최종 리스트는 [0,0,0,0,0,1,0] 이런 식이다.

  • 네트워크 장애가 고쳐진 후에는 마지막 남은 음식인 6번 음식을 섭취하면 된다.

  • 시뮬레이션을 쉬운 리스트로 한 것 같은데, 일단 맞는 내용 같다.

3. 주요 포인트

  1. x바퀴만큼 돌고, 마지막 인덱스에 도착하는 시간이 몇초인지 알면, 남은 초로 다음 인덱스를 구할 수 있다.
  2. 최소인 인덱스x리스트 수 만큼 빼주는걸 x만큼 반복하면, 남은 초로 다음 인덱스를 구할 수 있다.

4. 구현 과정

  1. 1번방식으로 풀면 마지막 인덱스에 도착할때 걸린 시간이 최대이면서 k보다 작아야 할 것 이다.
    위같은 경우라면 28초가 최대이며, 마지막 인덱스에 7번째 도착할 때가 최대라는 얘기이다.
    그렇다면 수의 가감없이 그냥 7바퀴를 돌았다고 가정을 해보자. 남은 수들은 어떻게 될까?

  2. [-5,-3,-4,-6,-2,1,-1] 이처럼 나오게 된다. 음수는 건너뛴 횟수를 의미한다. -> 이 음수를 모두 더한다면 총 건너뛴 횟수를 알 수 있다. 위같은 경우는 총 21번이다.

  3. 전체 7바퀴를 도는 동안 21번 건너뛰었으니 총 움직인 횟수(음식수x7바퀴)에서 빼줘본다.
    49 - 21 = 28로 정확하게 나온다. 이미 시뮬레이션이 끝나서 알 수 있는 것 처럼 보이지만 조건식을 통해 충분히 찾을 수 있다.

  4. 몇바퀴인지만 알면 되니 반대로 탐색을 통해 몇 바퀴를 돌아야 최대 바퀴수인지를 찾으면 된다.
    즉, 리스트에서 각 인덱스에 몇을 빼야 최대 시간이면서 k보다 작은 수 인지 알면 된다는 말이다.

  5. 리스트의 최대값보다 높은 바퀴 수를 돌면 안되고, 반대로 최소값보다 작은 바퀴 수도 안된다.
    그렇다면 최소,최대값 사이에서 특정한 값을 구하는 문제가 된다는 뜻이다. -> 이분탐색을 사용한다.

  6. 이분탐색을 통해 총 몇바퀴 째에 우리가 원하는 값이 나오는지 찾아낸다.
    몇바퀴인지 알아냈다면, 리스트를 구한 바퀴 수만큼의 수를 전부 빼준 리스트로 바꾼다.

  7. 그 후 리스트 전체를 한번 탐색하며, 남은 초로 어느 인덱스에서 멈추는지 찾아내면 끝이다.
    위의 방식처럼 코드를 작성해 보겠다.

#1번째 풀이
def solution(food_times, k):
    if k >= sum(food_times): 
        return -1

    low, high = 0, 1000000000  #문제에서 주어진 원소의 최소, 최댓값
    laps, total_times, food_count = 0, 0, len(food_times) 바퀴 수, 총 시간, 음식 수
    while low <= high: # 평범한 이분 탐색문
        mid = (low + high) // 2
        times = food_count * mid #mid바퀴만큼 돌았을때의 시간
        for i in food_times: #음식 시간을 돌면서
            cnt = i - mid #음식 시간-바퀴 수를 해준다.(1바퀴당 1초기 때문)
            if cnt < 0: #음수이기에 건너 뛰어야 하는 상황이라면
                times += cnt #총 걸린 시간에 음수를 더해 시간을 줄여줌
        if times <= k: # 총 시간이 k보다 작거나 같다면, 우리가 원하는 바퀴 수일 수 있으니 각각 저장해준다.
            laps, total_times = mid, times
            low = mid + 1 #k보다 작으면서 최대인 값이 아닐 수 있으므로 다시 이분 탐색
        else:
            high = mid - 1
    food_times = [i - laps for i in food_times] #최적의 바퀴 수만큼 뺀 리스트를 만들어준다.

    for i in range(food_count): 
        if food_times[i] > 0 and total_times == k: #음식이 남아 있고, 총 시간이 k를 만족할 경우
            return i+1 #현재 인덱스+1을 출력(0부터 시작하기 떄문)
        else:
            if not food_times[i] <= 0: #아닐 경우 음식이 남아 있는 경우만 총 시간에+1
                total_times += 1
    return -1
  1. 2번으로 풀면 매 바퀴마다 리스트 수만큼 총 시간에서 빼고, 최솟값을 제외하면 된다.

  2. 오름차순으로 정렬된 배열을 하나 만들어 최솟값->최댓값 순으로 정렬시킨다.

  3. 최솟값을 뽑아 최솟값x리스트 수 만큼의 시간을 k에서 빼준다.

  4. 최솟값이 빠졌으므로 현재 리스트의 맨 앞을 빼준다.

  5. 위 과정을 반복 하는데, 빼기전에 만약 k보다 최솟값x리스트가 더 크다면 반복문을 멈추고 나온다.

  6. 현재 k에서 남은 리스트 수만큼 mod해준다 -> 몇 번 후에 먹어야 될 음식이 있는지 확인

  7. food_times를 반복하면서 각 index의 값과 총 바퀴수를 비교해준다.

  8. 총 바퀴수보다 크다면, 현 index+1값을 결과 리스트에 넣어준다. -> 몇번째 음식이 남아 있는지 확인

  9. 어느 음식이 남아있는지 저장한 리스트에 mod 해준 값으로 위치 확인을 해준다.
    위의 방식으로 코드를 작성해 보겠다.

#2번째 풀이
def solution(food_times, k):
    if k >= sum(food_times):  # 첫번째 종료 조건
        return -1

    sort_ft = sorted(food_times)
    food_count = len(food_times)
    current_laps = 0
    total_laps = 0
    total_time = 0
    for food_time in sort_ft:
        current_laps = food_time - total_laps # 돌아야 하는 바퀴수 - 이전에 돌았던 바퀴수
        total_time += current_laps * food_count # 한바퀴 돌동안의 시간
        if k < total_time: # 주어진 시간보다 총 시간이 길어졌다면
            total_time -= current_laps * food_count # 방금 더해준 시간만큼 빼주고 반복문 빠져나오기
            break
        food_count -= 1 # 최솟값이 빠졌기 때문에 남은 음식 수를 빼준다.
        total_laps = food_time  # 방금 돌게 된 바퀴 수를 총 바퀴 수로

    k -= total_time # 최대로 돈 바퀴 수만큼의 시간을 뺌
    remain_count = k % food_count # 나머지를 구함으로써 몇번 더 갈 수 있는가 확인

    result = []
    for index, remain_food in enumerate(food_times): 
        if total_laps < remain_food: # 총 돌게된 바퀴수보다 남은 음식 시간이 크다면
            result.append(index+1) # 리스트에 현재 index+1을 해준다. (0부터 시작하므로)
   
    return result[remain_count]  # 아까전 구한 값이 마지막 인덱스 값이 어딘지 알려줌

🤔생각

  • 한번에 통과하지는 못했다. 논리 설계는 나름 잘 구현했다고 생각했는데, 그걸 코드로 옮기는 과정에서 어려움을 겪었다. 구현 문제를 많이 안 풀어본 탓인 것 같다..

  • 1번 방식은 최소, 최댓값을 food_times의 값으로 했더니 문제가 생겼었다. 디버그를 통해 알게 된 후, 0과 1000000000(문제에서 준 조건)값으로 바꿨더니 통과하였다.

  • 2번 방식은 논리 설계를 구현하는 과정에서 굉장히 애먹었는데, 1번 방식으로 문제를 통과하고 보여준 다른 사람의 풀이를 보고 구현에 성공했다!😭(내 생각과 똑같았던 코드라서 90%는 비슷하게 짠 거 같다🙄)

  • 시간도 시간대로 많이 걸렸고, 문제도 엄청 많이 틀렸다. 디버그를 해도 안 보일 때도 적지 않아서 부족함을 많이 느낀 문제였다. 더 많은 문제를 풀으면서 경험 쌓기를 해야겠다..!😤

profile
하하

0개의 댓글