Q06 무지의 먹방 라이브

domybest·2021년 4월 10일
0

실전 문제

목록 보기
6/34

문제
풀이 코드

알고리즘

일단 음식을 다 먹는데 걸리는 시간을 기준으로 오름차순 정렬을 진행하자. 그 후 앞에서 부터 반복하여 K번 안에 이 음식을 다 먹을 수 있는지를 차례로 확인하고 K번 안에 음식을 다 먹을 수 없는 부분에서 반복문을 종료한다. 그 후 '남은 횟수' 만큼 '남은 음식' 에 대하여 먹는 행위를 반복하면 정답을 구할 수 있다.

먼저 K번의 횟수가 음식 전체를 하나씩 먹지도 못할 경우가 있을 것이다. 이 때는 문제에서 주어진 조건에 따라 -1을 리턴하고 함수를 끝내면 된다.

	long sum = 0;
        for(int i = 0; i < food_times.length; i++)
            sum += food_times[i];
        // 모든 음식을 다 먹게 될 경우
        if(sum <= k)
            return -1;

여기서 중요한 부분이 있다. 정확성 테스트에서는 문제 없지만 효율성 테스트의 조건을 확인 해보면 k가 2 * 10^13 이하의 범위를 가지기 때문에 이로 인해 영향을 받는 변수들은 전부 long 형으로 선언 해 주어야 한다는 것이다. sum은 food_times 배열의 모든 원소를 더하는 것인데 이는 충분히 int형 표현 범위(약 21억)를 초과할 수 있기 때문에 long 형으로 선언 해야 한다.이 부분을 간과하여 효율성 테스트에서 계속 불합격을 받았다. 항상 기본 개념에 충실하자는 것을 기억하자.

음식 정보를 어디에 저장할까를 고민 해 보면 List 형태에 해도 되고 PriorityQueue에 저장해도 되지만 List형태에서는 효율성 테스트 2가지에서 시간초과를 야기한다. 이유는 삽입과 삭제 연산이 필요할 때 O(n)과 O(logn)으로 비용차이가 나기 때문이다. 따라서 효율성을 극대화하기 위해 PriorityQueue 자료구조를 사용하는 것이 적절하다. 다만 마지막 남은 음식들을 처리할 때는 따로 ArrayList 자료구조가 필요하다. 왜냐하면 정렬 기준을 시간에서 음식 번호로 바꾸는 과정이 자바의 PriorityQueue 에서는 어려운 과정이기 때문이다.

// 먹는데 가장 짧은 시간이 걸리는 것부터 확인해서 k 시간 안에 다 먹는지 계산 해 나감.
        // 지금까지 걸린 시간 + (현재 탐색하는 음식 다 먹는데 걸리는 시간 - 이전 음식 먹는데 걸린 시간) * 남은 덜 먹은 음식 개수 <= k
            while(sum_time + ((queue.peek().time - previous) * remainder) <= k){
        	now = queue.poll().time;
            	sum_time += (now - previous) * remainder;
            	remainder -= 1;
            	previous = now;
        }

위에서도 언급했지만 문제 효율성 테스트에서는 k가 2 * 10^13 = 2조, 즉 int형 표현 범위를 벗어나기 때문에 이에 영향 받는 '모든' 변수는 long 형으로 선언이 되어야 한다. 파이썬에서는 생각할 필요 없지만 자바로 코딩테스트를 진행 중이기 때문에 반드시 long형으로 선언해야 함을 주의하자.

	int remainder = food_times.length; // 남은 음식 개수
        long sum_time = 0; // 해당 과정까지 총 걸린 시간
        long previous = 0; // 현재 단계 이전까지 걸린 시간
        int now;
  1. 남은 음식의 개수는 k와 관련 없이남은 음식의 개수는 k와 관련 없이 길이가 20만 이하라고 했으므로 int형으로 해도 상관 없다.
  2. 효율성 테스트에서 food_times 각 원소는 1억의 값까지 가능하므로 총합은 분명 int형 범위를 충분히 벗어날 가능성이 존재하므로 반드시 long형으로 선언해야 한다.
  3. previous 변수 역시 이전 단계 sum_time 값을 저장하므로 long형으로 선언하여야 한다.
  4. now 변수는 현재 살펴보는 음식을 다 먹을때까지 걸리는 시간이므로 최대 1억의 값이다. 따라서 int형으로 선언해도 상관 없다.
    이런식으로 꼭 변수 형도 같이 고려해 주어야 겠다.

해당 문제는 카카오해당 문제는 카카오 블라인드 채용 코딩테스트 문제이다. 처음으로 카카오 문제를 풀어 보았는데 열심히 연습해야 겠다는 생각이 든다.

profile
기억할 때 까지 반복!

0개의 댓글