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

package com.ji.beakjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

public class Virus {

	static int computerCnt, connectPairCnt;
	static int[][] graph;
	static boolean[] DFSisVisited;
	static List<Integer> DFSvisitArr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		computerCnt = Integer.parseInt(br.readLine());// 노드 갯수
		connectPairCnt = Integer.parseInt(br.readLine()); // 간선 갯수
		graph = new int[computerCnt + 1][computerCnt + 1];
		DFSisVisited = new boolean[computerCnt + 1]; //방문 정보 초기화

		DFSvisitArr = new ArrayList<Integer>();

		for (int i = 0; i < connectPairCnt; i++) {
			String[] comPairNum = String.valueOf(br.readLine()).split(" ");
			int a = Integer.parseInt(comPairNum[0]);
			int b = Integer.parseInt(comPairNum[1]);
			graph[a][b] = 1;
			graph[b][a] = 1;
		}

		for (int i = 0; i < computerCnt + 1; i++) {
			DFSisVisited[i] = false;
		}

		dfs(1);

		Integer result = DFSvisitArr.size() - 1;
		bw.write(String.valueOf(result));

		br.close();
		bw.flush();
		bw.close();

	}

	static void dfs(int nodeNum) {
		// 방문한 노드 번호에 대한 boolean 처리
		DFSisVisited[nodeNum] = true;
		// 방문한 순서에 대한 노드 정보 리스트 저장
		DFSvisitArr.add(nodeNum);
		for (int i = 1; i <= computerCnt; i++) {
			if (graph[nodeNum][i] == 1 && DFSisVisited[i] == false) {
				dfs(i);
			}
		}
	}

}

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

쉬워 보이지만 결국에는 정규식을 얼마나 잘 사용하냐를 보는 문제 같습니다. 

정규식 사용을 위해서 여러 블로그를 참고하여서 풀게 되었습니다.

package com.ji.test;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

import com.ji.study.RecommNewId;

public class RecommNewIdTest {
	
	@Test
	void test() {
		
		RecommNewId test = new RecommNewId();
		
		assertEquals("bat.y.abcdefghi", test.solution("...!@BaT#*..y.abcdefghijklm"));
		assertEquals("z--", test.solution("z-+.^."));
		assertEquals("aaa", test.solution("=.="));
		assertEquals("123_.def", test.solution("123_.def"));
		assertEquals("abcdefghijklmn", test.solution("abcdefghijklmn.p"));
		
	}

}

package com.ji.study;

public class RecommNewId {

	public static String solution(String new_id) {
		 String answer = new_id.toLowerCase(); // 1단계

	        answer = answer.replaceAll("[^-_.a-z0-9]", ""); // 2단계
	        answer = answer.replaceAll("[.]{2,}", "."); // 3단계
	        answer = answer.replaceAll("^[.]|[.]$", "");    // 4단계
	        
	        if (answer.equals("")) {    // 5단계
	            answer += "a";
	        }

	        if (answer.length() >= 16) {     // 6단계
	            answer = answer.substring(0, 15);
	            answer = answer.replaceAll("[.]$","");
	        }

	        if (answer.length() <= 2) {  // 7단계
	            while (answer.length() < 3) {
	                answer += answer.charAt(answer.length()-1);
	            }
	        }

	        return answer;
	}
	


}

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;
	}

}