카카오 블라인드 채용 신입 공채 1차 코딩 테스트) 3번 문제

문제 출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

지난 9월 16일(토) 오후 2시부터 오후 7시까지 5시간동안 진행한 코딩테스트입니다.

보통 코딩 테스트 문제 유출하면 안되는데, 카카오는 문제를 공개하고 직접 문제 해설도 진행했습니다.

시험 당시 제출했던 코드와 해설을 참고하여 수정한 코드를 올리겠습니다.

이것 또한 공부가 되겠죠.

"LRU 캐시"라는 단어가 나오자마자 나중으로 제꼈던 문제 입니다.

다른문제를 풀고나서 이 문제를 다시 보니 너무나 쉬운 문제였습니다.

저 처럼 "LRU 캐시"라는 용어의 압박감을 느꼈던 분들이 많으실거 같아요.

해당 문제를 포스팅 하고 나서 "LRU 캐시"를 구현한 코드를 찾아봐야겠네요.

함정은 "캐시 사이즈 = 0" 일때 입니다.

public class kakao3 { public static void main(String[] args) { solution(5,new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}); solution(2,new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}); solution(0,new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}); } public static int solution(int cacheSize, String[] cities) { LinkedList<String> cache = new LinkedList<String>(); int time = 0; for (int i=0; i<cities.length; i++) { String city = cities[i].toUpperCase(); //모두 대문자로 변환 if (cache.contains(city)) { //캐시 안에 city가 존재할 경우 cache.remove(city); cache.add(city); time +=1; } else { //캐시 안에 city가 존재하지 않을 경우 if(cacheSize == 0){ //캐시 사이즈가 0일 경우  } else if ( cache.size() < cacheSize) { cache.add(city); } else { cache.remove(0); cache.add(city); } time +=5; } } System.out.println(time); return time;     } }

LRU 캐시를 구현해본적이 없어서 주어진 문제 조건에 맞는

코드를 구현했습니다.

(실제로는 캐시 탐색 후 적중 실패하면 추가 작업을 수행하지만

제가 짠 코드는 캐시 구현 방식이 아닙니다.)

자바 자료구조를 사용해서 그런지

코드는 많이 간단 했습니다.

- 추가 코드 (17년 10월 25일)-

import java.util.LinkedList; public class Q3 { public static void main(String[] args) { solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}); solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}); solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}); solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}); solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}); solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}); } public static void solution(int cacheSize, String[] cities) { LinkedList<String> cache = new LinkedList<>(); int time = 0; for ( int i = 0; i < cities.length; i++ ) { String tempCity = cities[i].toLowerCase(); if ( cache.contains(tempCity) ) { //HIT cache.remove(tempCity); cache.add(tempCity); time += 1; } else { //MISS if ( cacheSize > 0 ) { if ( cache.size() == cacheSize ) { cache.removeFirst(); } cache.add(tempCity); } time += 5; } } System.out.println(time); } }

cache miss일때의 코드를 더 다듬었습니다.

2018년 1월 26일 public class kakao3 { public static void main(String[] args) { solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}); solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}); solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}); solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}); solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}); solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}); } static void solution(int size, String[] city) { LinkedList<String> cache = new LinkedList<>(); int time = 0; for (int i = 0; i < city.length; i++) { String nowCity = city[i].toUpperCase(); //캐시에 있으면 time += 1; if (cache.contains(nowCity)) { cache.remove(nowCity); cache.add(nowCity); continue; } //캐시에 없으면 time += 4; if (cache.size() < size) { cache.add(nowCity); } else if (size > 0) { cache.removeFirst(); cache.add(nowCity); } } System.out.println(time); } } Hit과 Miss로 구분하여 작동하는 로직

좀 더 좋은 코드 및 다듬을 부분을 알려주시면 감사히 학습하겠습니다.