[코딩테스트 - Java] 캐시, 튜플

요새 문제 풀고 포스팅을 안했는데, 간만에 여유가 생겨 포스팅을 해보고자 한다.

캐시 (LRU 알고리즘)

문제 설명을 요약하자면, DB 조회 시에 대량의 데이터를 효율적으로 가져오기 위해 필요한 캐시 알고리즘을 구현했을 때, 캐시 크기에 대한 실행시간을 구하는 문제이다.

이때, 캐시가 가득 찼을 때 교체하는 알고리즘은 페이징 처리 알고리즘에서 사용하는 LRU(Least Recently Used) 알고리즘을 사용한다고 한다. LRU는 사용한지 가장 오래된 것을 우선 순위로 교체해주는 알고리즘이다.

LRU는 cache miss일 경우 실행시간+5, cache hit일 경우 실행시간+1로 계산하는데, cache hit은 캐시 안에 특정 데이터가 있을 때를 말한다. 이 조건을 기준으로 구현했을 때 필요한 것은

1) 순서 : 사용된 순서를 표기하는 것이 필요하다. 또한, 최근 사용되었을 경우 순서를 최신화해야 하므로 순서를 바꿀 수 있는 자료구조가 필요하다.
2) 조건 : 조건에 맞는 실행시간 계산과 유동적인 자료구조 변화가 필요하다.

이를 종합하여 유연하고 순서가 있는 LinkedList로 구현하고자 했다. cache 크기는 0~30이기 때문에 LinkedList로 메모리 문제가 일어나진 않을 것이다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int runtime = 0;
        
        LinkedList<String> cache = new LinkedList<>();
        if(cacheSize == 0) return cities.length * 5;
        
        for(String city : cities){
            city = city.toUpperCase();
            // 캐시에 있을 때
            if(cache.contains(city)){
                cache.remove(city);
                cache.addLast(city);
                runtime++;
            }
            // 캐시에 자리가 있을 때
            else if(cache.size() < cacheSize){
                cache.addLast(city);
                runtime+= 5;
            }
            // 교체해야 할 때
            else{
                cache.removeFirst();
                cache.addLast(city);
                runtime += 5;
            }
        }
        return runtime;
    }
}

이 문제에서 처음 LinkedList 클래스를 사용해보았는데 사용법이 간단하고 유용한 것 같아 따로 정리해보겠다.

튜플

문제 설명은 아래와 같다.

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다.
중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.
원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.
{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}
특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

문제가 난해한 것이...순서에 대한 자세한 설명이 안나와있어 고민하는 시간이 길었다. 그렇지만 요소를 찾는 것에 큰 어려움은 없었지만, 입력 값이 "{}"로 이루어진 집합을 문자열로 나타낸 것이라 문자열 파싱에 더 오랜 시간이 걸렸다.

문제 풀이 순서는 이러하다.

1) 문자열을 파싱한다.
2) 요소가 적은 순으로 정렬한다.
3) Set(집합) 클래스를 사용하여 중복 제거 후 추가한다.

위의 풀이에 주의사항은 Set 또는 HashSet에 순서가 없으므로 순서가 있는 LinkedHashSet을 사용하는 것이 중요하다. 또한 앞서 서술했듯이 문자열을 파싱하여 원하는 집합의 요소들만 가져오는 것이 중요하다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        ArrayList<Integer> answer = new ArrayList<>();
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        
        s = s.substring(2, s.length()-2);
        String[] strArr = s.split("\\},\\{");
        Arrays.sort(strArr, (e1, e2) -> e1.length() - e2.length());
        
        for(String str : strArr){
            for(String ele : str.split(",")){
                set.add(Integer.parseInt(ele));
            }
        }
        
        
        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}

포스팅하지 못한 문제들은 난이도가 높거나 시간이 부족해 올리지 못했는데, 되새길만한 문제들은 추가적으로 포스팅할 예정이다.