[Swift] 프로그래머스, 무지의 먹방 라이브

문제 링크

무지의 먹방 라이브

잡담

또 카카오 문제.. 제가 원래 목표가 하루에 알고리즘 문제 2개 풀기입니다.. 그런데 자꾸 카카오 문제만 풀면 한 문제 풀고 방전이에요.. 🤣

이번 문제도 역시나 못풀었습니다.. 알고리즘은 그리디 알고리즘이라고 하네요!

그럼 저의 푸념은 그만 듣고, 바로 풀이로 넘어가 볼까요??

풀이

결국 풀지 못해서 블로그와 유튜브를 참고 했습니다.

처음엔

참고 블로그

이 분의 블로그에서 코드를 봤는데, 이해가 안돼서 유튜브를 봤습니다.. ㅎㅎ 쉽지 않네요.. 역시 카카오

참고 유튜브

그래서 유튜브 강의 영상을 보는데, 이게 java 기반으로 코드를 짜긴하지만 저는 원리 자체에 대해서만 학습했습니다.

아래에 첨부될 이미지는 유튜브에서 가져왔습니다.

처음에 받아오는 시간이 담긴 배열을 오름차순으로 정렬해야 합니다. 그 이유는 어차피 결국 시간이 많이 남은 음식을 먹어야 하니까요!

그림을 보시면 저렇게 정렬된 모습을 보실 수 있는데요. 이때, 정렬되기 전의 인덱스를 기억하기 위해서 저는 튜플 형태로 배열을 만들어서 정렬해줬습니다.

첫 번째 element는 인덱스 3과 시간은 1인 값을 가지고 있어요. 약간 테트리스 처럼 생각하시면 편할 것 같아요!

시간 순서대로 정렬을 했기 때문에 1보다 작은 시간을 가지고 있는 element는 존재하지 않습니다. 그렇기 때문에 모든 배열을 한 바퀴 돌아야한다는 소린데요..

이거를 그냥 (배열의 길이 - i * time ) 으로 계산해서 이 값을 k에서 빼주면 됩니다.

그러면 가장 밑에 줄이 사라진다고 생각하시면 돼요! 마치 테트리스처럼요.

여기서의 time은 이전 time에서 현재 time을 뺀 값이라고 생각하시면 됩니다.

이런 식으로 계속 k를 빼면 결국 값이 k보다 큰 경우가 발생하는데, 이 경우엔 루프를 나와서

남은 배열을 다시 element의 index 순서로 정렬하고 k번만큼 순회를 통해 찾아도 상관 없습니다만..

(k % 배열길이) 번 째의 element의 index가 방문해야하는 인덱스라고 하네요!

이건 수학적인 원리로 이렇게 계산한 것 같은데, 음.. 저도 수학은 잼병이라 원리를 설명해드릴 순 없지만, 직접 손으로 계산해보면 맞는거 같더라구요 ㅋㅋㅋ

코드

//
//  main.swift
//  무지의먹방라이브
//
//  Created by 남기범 on 2020/12/29.
//  Copyright © 2020 남기범. All rights reserved.
//

import Foundation

func solution(_ food_times:[Int], _ k:Int64) -> Int {
    guard food_times.reduce(0, +) > k else {
        return -1
    }
    
    var dic: [(time: Int, idx: Int)] = food_times.enumerated().map { ($1,$0) }
        .sorted(by: <)
    
    var k = Int(k)
    var i = 0, j = 0, cycle = 0
    
    while i<dic.count {
        while j < dic.count
                    && dic[i].time == dic[j].time {
            j += 1
        }
        
        let timeDiffer = dic[i].time - cycle
        let eatCount = timeDiffer * (food_times.count - i)
        
        if eatCount > k {
            break
        }
        
        cycle += timeDiffer
        k -= eatCount
        i = j
    }
    
    dic = dic[i...].sorted(by: { $0.idx < $1.idx })
    
    return dic[k%dic.count].idx+1
}