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

2019 카카오 채용 코딩 테스드 문제입니다.

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

문제 확인

 

알고리즘을 사용하여 푸는 것보다 계산식과 몇 개의 루프 문을 통해 푸는 것이 훨씬 성능이 좋습니다.

 

풀이

 

 

 

위와 같은 식으로 모든 루프를 처리하면 정확도 테스트도 통과하기 어렵습니다. 배열에 접근, 원소 수정과 함께 모든 루프를 돌게 되므로 O(n^2)이 되기 때문입니다.

 

따라서 각 루프 문을 압축하여 가능한 루프를 한 번에 처리해야 합니다.

 

food_times 배열의 길이를 length로 두고 k와 비교하여 몇 번의 루프를 돌고 난 후 몇 번을 움직이는지 확인하여 풉니다.

• 루프 횟수 : k / length
• 남은 움직임 횟수 : k % length

이를 통하여 루프 횟수 loop 보다 낮거나 같은 food_times 원소를 0으로 만들어 둡니다. 이때 0으로 만든 원소는 다음 루프에서 세면 안되기 때문에 루프를 도는 동안 0 원소를 지나친 수를 남은 움직임 횟수 move에 더해줍니다.

 

 

5개의 원소가 0이 되었으므로 length는 3이 되고 이는 move보다 크므로 추가 루프가 발생하여 위 과정을 반복합니다.

반복하는 과정에서 length가 0이 되면 더 이상 먹을 수 있는 음식이 없으므로 -1을 반환합니다.

 

모든 루프 처리가 끝나면 0을 제외한 원소들에서 move만큼 이동하여 해당 인덱스를 반환합니다.

 

코드

#include <iostream>
 
#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<int> food_times, long long k) {
    int n = food_times.size(), len = n;
 
    //loop : 루프 횟수, move : 남은 움직임 횟수
    long long loop = k / n, move = k % n;
    while (1) {
        for (int i = 0; i < n; i++) {
            if (!food_times[i])continue;//visited
            if (food_times[i] <= loop) {//루프 횟수보다 원소가 작으면
                move += loop - food_times[i];//차이만큼 추가 움직임 필요
                food_times[i] = 0;//visited
                len--;//남은 음식의 종류 --
            }
        }
        if (!len)//남은 음식이 없으면
            return -1;
        if (move >= len) {//움직임 횟수가 남은 음식의 종류보다 많으면 추가 루프 발생
            loop += move / len;
            move %= len;
        }
        else break;
    }
    for (int i = 0; i < n; i++) {//음식 위치 찾기
        if (!food_times[i])continue;
        if (!move)
            return i + 1;
        move--;
    }
    return -1;
}
 
int main() {
    vector<int> t = { 5, 6, 7, 8, 9, 10 };
    int i = solution(t, 40);
    cout << i;
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.84MB)
테스트 2 〉	통과 (0.01ms, 3.96MB)
테스트 3 〉	통과 (0.01ms, 3.95MB)
테스트 4 〉	통과 (0.01ms, 3.96MB)
테스트 5 〉	통과 (0.01ms, 3.77MB)
테스트 6 〉	통과 (0.01ms, 3.95MB)
테스트 7 〉	통과 (0.01ms, 3.94MB)
테스트 8 〉	통과 (0.01ms, 3.98MB)
테스트 9 〉	통과 (0.01ms, 3.71MB)
테스트 10 〉	통과 (0.01ms, 3.91MB)
테스트 11 〉	통과 (0.01ms, 3.84MB)
테스트 12 〉	통과 (0.01ms, 3.96MB)
테스트 13 〉	통과 (0.01ms, 3.94MB)
테스트 14 〉	통과 (0.01ms, 3.9MB)
테스트 15 〉	통과 (0.01ms, 3.96MB)
테스트 16 〉	통과 (0.01ms, 3.96MB)
테스트 17 〉	통과 (0.01ms, 3.98MB)
테스트 18 〉	통과 (0.01ms, 3.96MB)
테스트 19 〉	통과 (0.01ms, 4.05MB)
테스트 20 〉	통과 (0.01ms, 3.97MB)
테스트 21 〉	통과 (0.01ms, 3.96MB)
테스트 22 〉	통과 (0.01ms, 3.96MB)
테스트 23 〉	통과 (0.01ms, 3.93MB)
테스트 24 〉	통과 (0.02ms, 3.91MB)
테스트 25 〉	통과 (0.01ms, 3.91MB)
테스트 26 〉	통과 (0.04ms, 3.95MB)
테스트 27 〉	통과 (0.03ms, 3.96MB)
테스트 28 〉	통과 (0.01ms, 3.95MB)
테스트 29 〉	통과 (0.01ms, 3.96MB)
테스트 30 〉	통과 (0.01ms, 3.96MB)
테스트 31 〉	통과 (0.01ms, 3.97MB)
테스트 32 〉	통과 (0.01ms, 3.97MB)

효율성 테스트

테스트 1 〉	통과 (3.20ms, 10.4MB)
테스트 2 〉	통과 (0.66ms, 10.4MB)
테스트 3 〉	통과 (4.94ms, 10.3MB)
테스트 4 〉	통과 (5.02ms, 10.4MB)
테스트 5 〉	통과 (3.18ms, 10.3MB)
테스트 6 〉	통과 (2.46ms, 10.4MB)
테스트 7 〉	통과 (3.68ms, 10.4MB)
테스트 8 〉	통과 (1.42ms, 10.5MB)

채점 결과

정확성: 42.9

효율성: 57.1

합계: 100.0 / 100.0