2019 카카오 블라인드 코딩테스트 (프로그래머스, Java, 무지의 먹방 라이브)

4. 무지의 먹방 라이브

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스

알고리즘 설명:

효율성이 중요한 문제.

하나하나 k를 탐색하기보다는 음식 개수가 적은 순으로 정렬 후 차례대로 탐색하면서 음식 개수 * 전체 음식 종류 수만큼 k값에서 빼주면 되는 문제

• Food라는 클래스를 만들어 인댁스와 음식 개수를 관리

• LinkedList에 클래스들을 넣고 음식 개수 순으로 정렬

• Iterator로 차례대로 리스트에 접근하여 음식 수를 가져와 리스트에 남아있는 음식 수(list.size())만큼 곱하여 k에서 빼준다 
  • 그냥 음식 개수만 받아와 빼는 경우 중복해서 이전에 뺀 값이 또 빠지기 때문에 이전에 뺀 값을 음식 개수에서 빼준다. 
  • 작업 후 itr.remove()하여 리스트에서 지워준다.
  • k가 마이너스가 되는 경우 그 전에 break를 하여 반복문에서 빠져나온다.
• k값이 남은 음식 종류 수보다 많은 경우 어차피 한 바퀴 돌면 제자리가 되므로 k값을 음식 종류 수만큼 나눠 나머지 값으로 바꾼다.
• list를 다시 index순으로 정렬 후 리스트의 k번째 index에 들어있는 클래스의 index를 리턴해주면 정답.

막혔던 지점:

List를 만들 때 아무생각없이 ArrayList로 만들었다. 그 결과 효율성에서 대거 실패... List를 LinkedList로 바꾸니까 효율성 2번 빼고 다 통과되었다. ArrayList는 탐색에서 빠르고 LinkedList는 삽입과 삭제에서 빠르다.

 

효율성 2번은 k가 Long타입으로 들어오는데 (time - pre) * list.size()로 바로 계산하여 long에 집어 넣던 것을 time - pre 부분을 따로 Long타입 변수에 받아 list.size()와 곱하니 해결되었다. Long타입이 나오면 int 계산에 주의해야겠다....

 

코드(Java)

package programmersTest.org;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class MuziMukbangLive {

	public int solution(int[] food_times, long k) {
		List<Food> list = new LinkedList<>();
		for (int i = 0; i < food_times.length; i++) {
			list.add(new Food(i + 1, food_times[i]));
		}

		Collections.sort(list, new Comparator<Food>() {
			public int compare(Food fo1, Food fo2) {
				return fo1.time - fo2.time;
			}
		});

		Iterator<Food> itr = list.iterator();
		int pre = 0;
		while (itr.hasNext()) {
			int time = itr.next().time;
			long minus = time - pre;
			if (minus != 0) {
				long diff = minus * list.size();

				if (diff > k)
					break;

				k -= diff;
				pre = time;
			}
			itr.remove();
		}

		if (list.size() == 0)
			return -1;

		k %= (long) list.size();

		Collections.sort(list, new Comparator<Food>() {
			public int compare(Food fo1, Food fo2) {
				return fo1.index - fo2.index;
			}

		});

		return list.get((int) k).index;
	}

	public class Food {
		int index;
		int time;

		public Food(int index, int time) {
			this.index = index;
			this.time = time;
		}
	}

	public static void main(String[] args) {

	}

}