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

Problem

 

코딩테스트 연습 - 무지의 먹방 라이브

---

Solution

 

해당 문제는 효율성이 핵심인 문제입니다.

 

food_times가 최대 1억, k가 최대 2*10^13이기 때문에 단순히 0초부터 시간을 재며 음식을 확인하기엔 너무 큰 시간이 걸립니다.

 

 

1. 음식이 남지 않는 경우를 정의한다.

 

음식을 먹는 시간을 모두 합쳐도 k보다 작거나 같으면 k시간에 남는 음식이 없습니다.

 

if food_times.reduce(0,+) <= k { return -1 }

 

2. food_times를 인덱스와 시간으로 나눠 내림차순 정렬합니다.

 

정렬을 하게 되면 해당 시간이 담긴 음식이 몇 번째인지 모르기 때문에 Enum으로 만들어 index와 element를 나눠서 저장합니다.

 

var foods = food_times.enumerated().sorted{$0.element > $1.element}

 

3. 남은 음식 수와 최소 시간을 곱하여 k에서 빼준다.

 

한번에 음식 수를 가장 많이 뺄 수 있는 것은 현재 남은 음식 수와 가장 최소값을 곱해주면 됩니다.

 

즉, [3,5,6,7,8,9,4,4,3,3]가 있다고 가정하면 현재 남은 음식 수(10개) * 최소값(3)을 K에서 빼줄 수 있습니다.

 

그 다음은 가장 마지막에 삭제된 최소값을 저장해주고 K가 0보다 적을 때까지 반복해줍니다.

 

var last:Int = 0
    while K - foods.count * (foods.last!.element - last) >= 0{
        let min = foods.removeLast().element
        K -= (foods.count+1) * (min-last)
        last = min
    }

 

4. 인덱스 순으로 정렬하여 K를 남은 음식 수 만큼 나눈 것의 나머지번 째 인덱스를 반환합니다.

 

 return foods.sorted{$0.offset < $1.offset}[K%foods.count].offset + 1

---

Source Code

 

---

P.S

 

처음으로 프로그래머스 4단계를 풀었는데 가장 많은 사람이 푼 문제를 풀어서 그런지 3단계와 크게 다르지 않다고 느꼈다.

 

근데 위 문제에서 조금 이상한게 음식을 오름차순 정렬하고 첫 번째 원소를 사용해서 반복하면 효율성에서 시간 초과가 나오고

 

내림차순 정렬하여 마지막 번째 원소를 사용하면 통과가 된다... 왜 이러는거지..