프로그래밍/알고리즘 연습
(2018년)KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브(틀림)
by mrvan
2019. 1. 30.
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42891?language=java#
첫번째 방법 1. 알고리즘 - 큐(FIFO)를 이용하여 맨 앞에 있는 food를 먹고 해당 값을 맨 뒤로 보냄 - 만약 0이 됐다면 해당 index는 제거
2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import java.util.LinkedList; class Solution { public int solution(int[] food_times, long k) { int answer = 0; int count = 0; LinkedList<Integer> key = new LinkedList<Integer>(); LinkedList<Integer> value = new LinkedList<Integer>(); for(int i=1;i<=food_times.length;i++){ key.add(i); value.add(food_times[i-1]); } for(long i=0;i<k;i++){ int tkey=0; int tvalue=0; if(key.size()!=0){ tkey = key.get(0); tvalue = value.get(0); } if(key.size()!=0){ key.remove(); value.remove(); } tvalue=tvalue-1; if(tvalue!=0){ key.add(tkey); value.add(tvalue); } else{ count++; } if(count == food_times.length){ break; } } if(count==food_times.length) answer=-1; else answer = key.get(0); return answer; } } | cs |
3. 구현 방식 1. 두개의 LinkedList를 생성(key와 value)
2. key 와 value에 순서대로 값을 삽입 | ex) food_times = {2,1,5}라면 key = {1,2,3} value = {2,1,5} 이런식으로 key와 value값을 매칭시켜 삽입 | cs |
3. k초 만큼 for문 반복하며 value값 1씩 감소 시킨 후 list에 add | ex) food_times = {2,1,5}라면 최초 key = {1,2,3} value = {2,1,5} 0s~1s key = {2,3,1} value = {1,5,1} //key = 2 value = 1에서 value=0으로 변경되었으니 해당 index 삭제 1s~2s key = {3,1} value = {5,1} 2s~3s key = {1,3} value = {1,4} //key = 1 value = 1에서 value=0으로 변경되었으니 해당 index 삭제 3s~4s key = {3} value = {4} | cs |
ㄹ 4-1. 만약 k반복 전에 key.size()==0 이라면 answer = -1 4-2. 그렇지 않다면(k번 반복 완료) answer = key.get(0)
4. 결과 정확성 테스트 : 32/32 효율성 테스트 : 0/8
5. 원인 분석 (1) k번만큼 for문을 도는 것은 너무 비효율적이다.
6. 수정 (1) 전체 food_times 값이 k보다 작거나 같으면 answer=-1을 리턴 (for문전에 실시) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import java.util.LinkedList; class Solution { public int solution(int[] food_times, long k) { int answer = 0; int count = 0; long sum=0; LinkedList<Integer> key = new LinkedList<Integer>(); LinkedList<Integer> value = new LinkedList<Integer>(); for(int i=1;i<=food_times.length;i++){ key.add(i); value.add(food_times[i-1]); sum = sum +food_times[i-1]; } if(sum<=k){ answer = -1; return answer; } for(long i=0;i<k;i++){ int tkey=0; int tvalue=0; if(key.size()!=0){ tkey = key.get(0); tvalue = value.get(0); } if(key.size()!=0){ key.remove(); value.remove(); } tvalue=tvalue-1; if(tvalue!=0){ key.add(tkey); value.add(tvalue); } } answer = key.get(0); return answer; } } | cs |
|