구르는 돌에는 이끼가 끼지 않는다

https://programmers.co.kr/learn/courses/30/lessons/42862

package com.ji.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GymSuit {

	public static void main(String[] args) {
		System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 1, 3, 5 }));
		System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 3 }));
		System.out.println(solution(3, new int[] { 3 }, new int[] { 1 }));
		System.out.println(solution(3, new int[] { 1, 2 }, new int[] { 2,3 }));
	}

	public static int solution(int n, int[] lost, int[] reserve) {
		int answer = 0;

		Arrays.sort(lost);
		Arrays.sort(reserve);

		List<PersonVO> sendPossibleList = new ArrayList<PersonVO>();
		for (int i = 1; i <= n; i++) {

			PersonVO personVO = new PersonVO();
			personVO.setIndex(i);
			personVO.setTotal(1);

			if (Arrays.binarySearch(lost, i) >= 0)
				personVO.setTotal(personVO.getTotal() - 1);

			if (Arrays.binarySearch(reserve, i) >= 0)
				personVO.setTotal(personVO.getTotal() + 1);
			
			sendPossibleList.add(personVO);
		}

		for (int i = 1; i < sendPossibleList.size(); i++) {

			if (sendPossibleList.get(i).getTotal() > 1 && sendPossibleList.get(i - 1).getTotal() == 0) {
				sendPossibleList.get(i - 1).setTotal(1);
				continue;
			}
			
			if(i+1 >= sendPossibleList.size())
				continue;
			
			if (sendPossibleList.get(i).getTotal() > 1 && sendPossibleList.get(i + 1).getTotal() == 0) {
				sendPossibleList.get(i + 1).setTotal(1);
				continue;
			}

		}

		for (PersonVO vo : sendPossibleList) {
			if (vo.getTotal() > 0)
				answer++;
		}

		return answer;
	}

}

class PersonVO {
	Integer index;
	Integer total;

	public Integer getIndex() {
		return index;
	}

	public void setIndex(Integer index) {
		this.index = index;
	}

	public Integer getTotal() {
		return total;
	}

	public void setTotal(Integer total) {
		this.total = total;
	}

}

https://programmers.co.kr/learn/courses/30/lessons/17680

위 문제는 어떻게 보면 불친절한 문제입니다. 문제를 푸는 사람 입장에서 문제에서 말하는 [

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

]라는 전제 조거은 말근데로 캐기 교체 알고리즘을 풀지 않으면 풀수 없는 문제 입니다. 

예전에도 카카오 코테를 참여했을때도 다음 문제를 못풀었던 기억이 있네요. 

어쨋든 캐시 교체 알고리즘은 다음과 같습니다. 

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.

이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

라고 설명하고 있습니다. 

즉, 데이터의 접근을 빠르게 하기 위해서 나온 캐시 알고리즘이라고 생각하면 됩니다. 

캐시의 hits의 경우에는 캐시안에 데이터가 존재하므로 time값이 +1이 증가하고 

캐시 miss의 경우에는 캐시안에 데이터가 존재하지 않으므로 time값이 +5가 증가하게 됩니다. 

저는 다음과 같이 풀었습니다.

package com.ji.test;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

import com.ji.study.Cache;

public class CacheTest {
	
	@Test
	void test() {
		
		Cache test = new Cache();
		
		assertEquals(50, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(21, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
		assertEquals(60, test.solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(52, test.solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(25, test.solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(16, test.solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
		
	}

}

package com.ji.study;

import java.util.LinkedList;
import java.util.Queue;

public class Cache {
	
	public static int solution(int cacheSize, String[] cities) {
		int excuteTime = 0;
		Queue cacheQueue = new LinkedList<String>();

		if (cacheSize == 0) {
			excuteTime = cities.length * 5;
		} else {

			for (String city : cities) {
				city = city.toLowerCase();

				if (cacheQueue.contains(city)) {
					cacheQueue.remove(city);
					excuteTime++;
				} else {
					if (cacheQueue.size() >= cacheSize)
						cacheQueue.poll();
					
					excuteTime = excuteTime + 5;
				}
				
				cacheQueue.offer(city);
				
			}

		}

		return excuteTime;
	}

}

programmers.co.kr/learn/courses/30/lessons/42587

퇴근후 시간 날때마다 풀었습니다. 

가능하면 답을 안보고 풀기위해서 노력했습니다.

제일 중요한 것은 `문제를 완벽히 이해하는 것이다`라는 것을 깨달았습니다. 

문제의 의도를 파악하지 못해 계속 통과를 5일째 못하다가 아이패드에 그림을 그려가면서 이해하다보니

제가 놓친부분을 발견하고 결국 풀게되었습니다.(아이패드짱_구글 Jamboard짱)

package com.ji.study;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.List;

import org.junit.jupiter.api.Test;

public class PrinterTest {

	@Test
	void test() {

		Printer test = new Printer();

		assertEquals(5, test.solution(new int[] { 1, 1, 9, 1, 1, 1 }, 0));
		assertEquals(1, test.solution(new int[] { 2, 1, 3, 2 }, 2));
		assertEquals(6, test.solution(new int[] { 2,2,2,1,3,4 }, 3));

	}

}

package com.ji.study;

import java.util.ArrayList;
import java.util.List;

public class Printer {

	public static void main(String[] args) {

		int[] priori = { 1, 1, 9, 1, 1, 1 };
		int location = 0;
		System.out.println("result : " + solution(priori, location));

	}

	public static int solution(int[] priorities, int location) {
		int answer = 0;

		List<int[]> list = new ArrayList<int[]>();
		for (int i = 0; i < priorities.length; i++) {
			list.add(new int[] {i, priorities[i]});
		}

		List<int[]> result = getCompareNum(list);
		for (int j = 0; j < result.size(); j++) {
			if (result.get(j)[0] == location)
				answer = j;
		}

		return answer + 1;
	}

	public static List<int[]> getCompareNum(List<int[]> list) {

		for (int i = 0; i < list.size() - 1; i++) {
			for (int k = i + 1; k < list.size(); k++) {
				// 중요도가 높은 인쇄물이 있을 경우
				if (list.get(i)[1] < list.get(k)[1]) {
					return getCompareNum(shiftLastIndex(list, i));
				}
			}
		}
		
		return list;
		
	}

	// 가장 앞에 있는 대기 목록을 뒤로 이동
	public static List<int[]> shiftLastIndex(List<int[]> list, int moveIndex) {
		list.add(list.get(moveIndex));
		list.remove(moveIndex);
		return list;
	}

}