자바 - Map으로 코테 푸는 법

자바 코딩 테스트에서 어떻게 하면 Map으로 문제를 풀 수 있을까?

혹여나 지금 Map으로 아무 것도 못 하겠다 하더라도 괜찮다.

1번, 2번, 3번 계속 보고 하다 보면 할 수 있게 된다.

 

HashMap을 쓰는 법!

문제: 두 수의 합

문제 설명: 주어진 정수 배열 nums에서 두 수를 선택하여 그 합이 특정 목표값 target이 되도록 합니다. 두 수의 인덱스를 반환해야 합니다. 각 입력에 정확히 하나의 솔루션이 있다고 가정하고, 같은 요소를 두 번 사용할 수 없습니다.

 

입력 예시: nums = [2, 7, 11, 15], target = 9

 

출력 예시: [0, 1]

가장 좋은 솔루션

이 문제는 HashMap을 사용하여 각 숫자의 보완적인 숫자(목표값 - 현재 숫자)가 이전에 맵에 있는지 확인함으로써 효율적으로 해결할 수 있다.

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = sol.twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

 

TreeMap을 쓰는 법!

문제: 시험 성적 순위

문제 설명: 학생들의 시험 성적을 관리하는 시스템을 구축해야 합니다. 각 학생은 고유한 ID(정수)와 성적(정수)을 가지고 있습니다. 여러분은 다음 연산을 지원해야 하는 프로그램을 작성해야 합니다:

1. 학생의 성적을 추가하거나 업데이트합니다.
2. 특정 성적 범위(최소, 최대)에 해당하는 학생들의 ID를 찾습니다.

성적은 동일할 수 있으므로, 한 성적에 여러 ID가 매핑될 수 있습니다.

 

입력 예시:

add(123, 95)
add(124, 92)
add(125, 95)
find(90, 95) // 90점 이상 95점 이하의 성적을 가진 학생의 ID 반환

 

 

출력 예시:

[124, 123, 125]

 

가장 좋은 솔루션

TreeMap을 사용하여 성적을 키로, 해당 성적을 받은 학생들의 ID 목록을 값으로 하는 맵을 구성합니다. 성적 순으로 정렬되기 때문에 특정 범위를 쉽게 찾을 수 있습니다.

import java.util.*;

public class StudentScores {
    TreeMap<Integer, List<Integer>> scoreMap = new TreeMap<>();

    public void add(int id, int score) {
        List<Integer> ids = scoreMap.getOrDefault(score, new ArrayList<>());
        ids.add(id);
        scoreMap.put(score, ids);
    }

    public List<Integer> find(int minScore, int maxScore) {
        List<Integer> result = new ArrayList<>();
        scoreMap.subMap(minScore, true, maxScore, true).values().forEach(result::addAll);
        return result;
    }

    public static void main(String[] args) {
        StudentScores scores = new StudentScores();
        scores.add(123, 95);
        scores.add(124, 92);
        scores.add(125, 95);
        List<Integer> foundIds = scores.find(90, 95);
        System.out.println(foundIds);
    }
}

 

LinkedHashMap을 쓰는 법!

 

Java의 LinkedHashMap은 삽입 순서나 접근 순서를 유지하는 HashMap의 확장입니다. 이러한 특성은 순서가 중요한 문제를 해결할 때 특히 유용합니다. 다음은 LinkedHashMap을 활용하여 해결할 수 있는 코딩 테스트 문제와 그에 대한 최적의 솔루션을 제시합니다.

문제: 최소 캐시 교체 알고리즘(LRU Cache)

문제 설명: 최대 크기가 제한된 캐시를 구현해야 합니다. 이 캐시는 Least Recently Used (LRU) 교체 알고리즘을 사용하여, 가장 오래 전에 사용된 항목을 제거하고 새 항목을 추가합니다. 구현해야 하는 연산은 다음과 같습니다:

1. get(key): 키에 해당하는 값을 캐시에서 검색합니다. 키가 캐시에 존재한다면, 값을 반환하고, 그렇지 않으면 -1을 반환합니다.
2. put(key, value): 키와 값을 캐시에 삽입합니다. 만약 캐시가 꽉 차 있다면, 가장 최근에 사용되지 않은 항목을 제거하고 새 항목을 삽입합니다.

입력 예시:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

 

가장 좋은 솔루션

LinkedHashMap의 생성자를 사용하여 accessOrder를 true로 설정함으로써 LRU 캐시를 구현할 수 있습니다. 이 설정은 LinkedHashMap이 접근 순서를 유지하도록 합니다. 여기서는 또한 removeEldestEntry() 메서드를 오버라이드하여 캐시의 크기가 최대 크기를 초과할 때 자동으로 가장 오래된 항목을 제거하도록 합니다.

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // returns 1
        cache.put(3, 3); // evicts key 2
        System.out.println(cache.get(2)); // returns -1 (not found)
        cache.put(4, 4); // evicts key 1
        System.out.println(cache.get(1)); // returns -1 (not found)
        System.out.println(cache.get(3)); // returns 3
        System.out.println(cache.get(4)); // returns 4
    }
}

 

내부적인 동작을 자세히 살펴보면:

1. LinkedHashMap 생성자:
   1. new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) 코드는 LinkedHashMap의 특별한 생성자를 호출합니다.
   2. 이 생성자는 세 개의 매개변수를 받습니다:
      1. capacity: 초기 용량(여기서는 맵에 저장할 최대 엔트리 수를 의미하지만, 이는 loadFactor와 removeEldestEntry에 의해 제어됩니다).
      2. 0.75f: 로드 팩터(load factor), 맵이 얼마나 차 있을 때 재해싱(내부 데이터 구조를 재조정)을 할 것인지 결정하는 임계값.
      3. true: accessOrder 플래그, true로 설정하면 LRU(Least Recently Used) 순서로 엔트리를 정렬하게 됩니다(접근 순서).
2. removeEldestEntry 메서드:
   1. protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) 메서드는 LinkedHashMap에서 새로운 엔트리가 추가될 때마다 호출됩니다.
   2. 이 메서드는 맵의 크기가 용량을 초과하는지 여부를 판단하는 논리를 담고 있습니다. 즉, size() > capacity가 true를 반환하면 가장 오래된 엔트리(eldest)를 자동으로 제거해야 한다는 신호입니다.
   3. 여기서 중요한 점은, removeEldestEntry가 true를 반환하면 LinkedHashMap 자체가 자동으로 가장 오래된 엔트리를 맵에서 제거합니다. 따라서 이 메서드는 실제로 엔트리를 제거하지 않고, 제거할지 여부만 결정하며, 제거 작업은 LinkedHashMap이 처리합니다.

이러한 방식으로 LinkedHashMap은 자동으로 LRU 캐싱 메커니즘을 지원할 수 있으며, 맵의 크기 관리와 오래된 데이터의 자동 정리를 효율적으로 수행할 수 있습니다. 이 구현은 성능적으로도 유리하며, 복잡한 데이터 구조를 직접 관리하지 않고도 LRU 캐시를 손쉽게 구현할 수 있는 방법을 제공합니다.

 

아니, 도대체 어떻게 자동 제거가 돼? 🤯

 

LinkedHashMap의 자동 제거 기능은 Java의 LinkedHashMap 클래스 내부 구현에 의해 가능합니다. 이 기능을 이해하려면 LinkedHashMap의 특별한 특성과 내부 메커니즘에 대한 이해가 필요합니다.

LinkedHashMap의 내부 구현

1. 데이터 구조: LinkedHashMap은 해시 테이블과 연결 리스트를 결합한 형태로 구현되어 있습니다. 이 구조는 모든 엔트리(entry)들을 해시 테이블에 저장하여 빠른 검색을 가능하게 하면서, 동시에 연결 리스트로 엔트리들을 순서대로 관리하여 삽입 순서 또는 접근 순서를 유지합니다.
2. 접근 순서 관리: 생성자에서 accessOrder 매개변수를 true로 설정하면, LinkedHashMap은 엔트리에 접근할 때마다 해당 엔트리를 연결 리스트의 끝으로 이동시킵니다. 이는 최근에 접근한 엔트리가 리스트의 끝에 위치하게 되어, 가장 오래된 엔트리가 리스트의 시작 부분에 위치하게 만듭니다.
3. 엔트리 자동 제거: LinkedHashMap은 내부적으로 removeEldestEntry(Map.Entry<K,V> eldest) 메서드를 호출하여 엔트리를 추가할 때마다 리스트의 시작 부분에 있는 엔트리(가장 오래된 엔트리)가 제거될지 여부를 결정합니다. 사용자가 이 메서드를 오버라이드하여 조건을 지정하면, 이 조건에 따라 자동으로 가장 오래된 엔트리가 제거됩니다.

자동 제거의 실행 방식

• 엔트리 추가 시: 새 엔트리가 맵에 추가될 때, LinkedHashMap은 먼저 removeEldestEntry() 메서드를 호출하여 반환값을 검사합니다. 이 메서드가 true를 반환하면, 맵의 head (연결 리스트에서 가장 오래된 엔트리를 가리키는 포인터)가 가리키는 엔트리가 맵에서 제거됩니다.
• 메서드 오버라이드: 사용자는 removeEldestEntry() 메서드를 오버라이드하여, 맵의 크기가 특정 용량을 초과했을 때 true를 반환하도록 설정할 수 있습니다. 이렇게 설정하면, 맵의 크기가 용량을 초과하는 순간 자동으로 가장 오래된 엔트리가 제거됩니다.

이러한 메커니즘은 LinkedHashMap을 사용하여 LRU 캐시와 같은 데이터 구조를 구현할 때 매우 유용하며, 복잡한 관리 없이도 자동으로 가장 오래된 데이터를 관리할 수 있게 해 줍니다. 이는 Java의 객체 지향 설계와 데이터 구조의 효율적 관리를 잘 보여주는 예시입니다.

 

와~ 쉽지 않다! 😄

그리고 신기하다!

재밌다!!!

 

+ 마지막 추가 설명

 

LinkedHashMap 클래스는 생성자를 통해 초기 용량(initialCapacity), 로드 팩터(loadFactor), 그리고 항목의 순서를 결정하는 accessOrder 매개변수를 받을 수 있도록 오버로딩된 생성자를 제공합니다. 이러한 생성자를 사용하여 LinkedHashMap 인스턴스를 생성할 때, 이 세 가지 매개변수를 통해 LinkedHashMap의 동작 방식을 상세히 설정할 수 있습니다.

여기서 사용된 생성자는 다음과 같은 세 가지 매개변수를 받습니다:

1. initialCapacity: 맵의 초기 용량을 설정합니다. 이 값은 맵이 내부 데이터 구조를 확장하기 전에 저장할 수 있는 최대 요소 수를 정의합니다. 초기 용량을 적절히 설정하면 재해싱(해시 테이블의 크기를 조정하는 과정)으로 인한 성능 저하를 최소화할 수 있습니다.
2. loadFactor: 로드 팩터는 해시 테이블의 공간 사용률을 결정합니다. 일반적으로 로드 팩터는 0.75가 기본 값으로 사용되며, 이는 해시 테이블의 75%가 채워지면 크기가 확장된다는 것을 의미합니다. 로드 팩터를 높이면 공간 효율성이 증가하지만, 충돌의 가능성이 증가하여 성능이 저하될 수 있습니다.
3. accessOrder: 이 매개변수는 항목의 순서 유지 방식을 결정합니다. true로 설정하면 최근 접근 순서에 따라 항목이 재정렬되어 LRU(Least Recently Used) 캐싱 전략을 구현할 수 있습니다. false로 설정하면, 항목들은 삽입된 순서대로 유지됩니다.

이 생성자를 사용하여 LinkedHashMap의 인스턴스를 초기화하면, LRU 캐시와 같은 특수한 동작을 쉽게 구현할 수 있으며, 항목 추가, 접근 또는 제거 시의 순서에 따라 자동으로 가장 오래된 항목을 제거하는 로직을 적용할 수 있습니다. 이러한 기능은 특히 웹 캐시, 데이터 캐시, 기타 자원 관리 시스템에서 매우 유용하게 사용됩니다.