메모리: 78.5 MB, 시간: 2.76 ms - Answer Code1(23.01.31)
메모리: 81.4 MB, 시간: 2.66 ms - Answer Code2(23.02.20)
코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
ArrayList<String> cache = new ArrayList<>();
if(cacheSize == 0) // 캐시크기가 0
return cities.length * 5;
for(int i=0; i<cities.length; i++) {
cities[i] = cities[i].toUpperCase(); // 대소문자 구분X
if(cache.contains(cities[i])) { // cache hit
cache.remove(cities[i]);
cache.add(cities[i]);
answer += 1;
}
else { // cache miss
if(cache.size()==cacheSize) {
cache.remove(0);
cache.add(cities[i]);
}
else
cache.add(cities[i]);
answer += 5;
}
}
return answer;
}
}
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
List<String> cacheList = new ArrayList<>();
if(cacheSize == 0) {
return cities.length * 5;
}
for(int i = 0; i < cities.length; i++) {
cities[i] = cities[i].toLowerCase(); // 소문자로 변환
//cache hit
if(cacheList.contains(cities[i])) {
cacheList.remove(cities[i]);
cacheList.add(cities[i]);
answer += 1;
}
//cache miss
else {
answer += 5;
if(cacheList.size() == cacheSize) {
cacheList.remove(0);
cacheList.add(cities[i]);
}
else {
cacheList.add(cities[i]);
}
}
}
return answer;
}
}
LRU(Least Recently Used)에 대해 알고 있어야 풀 수 있는 문제였다.
LRU : 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.
LRU 알고리즘 구현을 보통 자료구조 Queue(큐)로 사용하면 편리하지만, Java에서는 LikedList가 Queue의 구현체이므로 Likedlist로 구현했다.
cache hit 인 경우(캐시에 존재한 경우) hit된 데이터를 기존 위치에서 가장 최근 위치로 이동 시킨다.(기존 위치를 제거하고 맨 뒤에 데이터를 추가한다)
cache miss 인 경우
새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일한다면, 꽉차있는 의미이므로 가장 오랫동안 사용하지 않은 것을 제거하고, 맨 뒤에 데이터를 추가한다.
새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일하지 않다면, 맨 뒤에 데이터를 추가한다.
메모리: 70.2 MB, 시간: 0.49 ms
코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
ArrayList<User> users = new ArrayList<>();
HashMap<String,Integer> suspendedList = new HashMap<>();
HashMap<String,Integer> idIdx = new HashMap<String,Integer>();
int idx = 0;
//각 유저에 대한 고유 index를 setting후 users ArrayList에 User 객체 추가
for(String name : id_list) {
idIdx.put(name, idx++);
users.add(new User(name));
}
//users의 idIdx.get(str[0])번째 index에 reportList에 피신고자 추가
//users의 idIdx.get(str[1])번째 index에 reportedList에 신고자 추가
for(String re : report){
String[] str = re.split(" ");
users.get(idIdx.get(str[0])).reportList.add(str[1]);
users.get(idIdx.get(str[1])).reportedList.add(str[0]);
}
//reportedList의 크기가 주어진 k와 같거나 크면 suspendedList의 피신고자 put
for(User user : users){
if(user.reportedList.size() >= k)
suspendedList.put(user.name,1);
}
//answer 배열 각 index에 해당하는 유저의 신고당한 횟수를 count up
for(User user : users){
for(String nameReport : user.reportList){
if(suspendedList.get(nameReport) != null){
answer[idIdx.get(user.name)]++;
}
}
}
return answer;
}
}
class User{
String name; //해당 유저명
HashSet<String> reportList; //피신고자 리스트
HashSet<String> reportedList; //신고자 리스트
public User(String name){
this.name = name;
reportList = new HashSet<>();
reportedList = new HashSet<>();
}
}
해당 문제를 제대로 이해하지 못한다면 2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설
를 참고하자.
메모리: 73.4 MB, 시간: 0.04 ms
코딩테스트 연습 > 2021 Dev－Matching：웹 백엔드 개발자（상반기）
import java.util.*;
public class Solution {
public int[] solution(int[] lottos, int[] win_nums) {
int[] answer = new int[2];
Map<Integer, Integer> compareRank = init();
int zero_count = 0, same_number = 0;
for (int i = 0; i < 6; i++) {
if (lottos[i] == 0) {
zero_count += 1;
continue;
}
for (int j = 0; j < 6; j++) {
if (lottos[i] == win_nums[j]) {
same_number += 1;
break;
}
}
}
answer[0] = compareRank.get(same_number + zero_count);
answer[1] = compareRank.get(same_number);
return answer;
}
private Map<Integer, Integer> init() {
Map<Integer, Integer> ret = new HashMap<>();
int rank = 6;
for (int i = 0; i <= 6; i++) {
if (i == 0 || i == 1) {
ret.put(i, rank);
continue;
}
rank -= 1;
ret.put(i, rank);
}
return ret;
}
}
메모리: 74.3 MB, 시간: 0.27 ms
코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT
class Solution {
public String solution(int[] numbers, String hand) {
StringBuilder sb = new StringBuilder();
int left = 10;
int right = 12;
for (int i = 0; i < numbers.length; i++) {
int n = numbers[i];
if (n == 1 || n == 4 || n == 7) {
left = n;
sb.append("L");
}
if (n == 3 || n == 6 || n == 9) {
right = n;
sb.append("R");
}
if (n == 2 || n == 5 || n == 8 || n == 0) {
if( n == 0 ) n = 11;
int leftDiff = (Math.abs(n - left) / 3) + (Math.abs(n - left) % 3);
int rightDiff =(Math.abs(n - right) / 3) + (Math.abs(n - right) % 3);
if (leftDiff == rightDiff) {
if (hand.equals("right")) {
right = n;
sb.append("R");
}else{
left = n;
sb.append("L");
}
} else if (leftDiff > rightDiff) {
right = n;
sb.append("R");
} else {
left = n;
sb.append("L");
}
}
}
return sb.toString();
}
}
StringBuilder() 클래스와 Math 클래스에 대해 다시금 개념을 복습하게 핸 문제였다.
다음 복습에는 조금 더 효율적이면서 깔끔한 코드를 만드는 것을 목표로 하자.
메모리: 77.8 MB, 시간: 0.43 ms
코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT
class Solution {
public int solution(String dartResult) {
int answer = 0;
String[] dart = dartResult.split("");
int[] score = new int[3]; // 점수
int index = -1; // score index
for(int i=0; i<dart.length; i++) {
// 숫자인지 확인
if(dart[i].matches("[0-9]")) {
index++;
score[index] = Integer.parseInt(dart[i]);
// 두자리 수 숫자?
if(dart[i+1].matches("[0-9]")) {
score[index] *= 10;
i++;
}
}
switch(dart[i]) {
case "D":
score[index] = (int)Math.pow(score[index], 2);
break;
case "T" :
score[index] = (int)Math.pow(score[index], 3);
break;
case "*" :
score[index] *= 2;
if(index - 1 >= 0) score[index-1] *= 2;
break;
case "#" :
score[index] *= -1;
}
}
for(int s : score) {
answer += s;
}
return answer;
}
}
배열로 변환해서 조건에 따라 if문과 switch-case문을 활용했다.
정규 표현식 방법과 switch-case문에 대한 이해만 알면 풀 수 있는 문제였다.