[알고리즘] 해시 알고리즘 패턴

여러개의 해시 문제를 풀면서 이 알고리즘 문제 유형의 패턴을 분석해보기로했다. 

1. 해시 알고리즘 문제인지 파악

문제에서 key와 value로 값으 저장해야한다면 해시 문제일 확률이 높다. 이럴 경우 HashMap 객체를 만들어서 그 안에 key와 value로 저장하고 활용하도록 한다.

2. 자주 사용하는 메소드

2.1 get, put, remove 메소드

map객체를 사용하는 기본 메소드이다. 각각 key값에 해당하는 값 조회, 입력, 삭제를 담당한다.

map.get(key);
map.put("값입력");
map.remove(key);

2. HashMap 객체 생성

아래 코드는 Key가 String이고, value가 Integer인 경우이다.

HashMap<String , Integer> map = new HashMap<>();

2.3 getOrDefault 메소드

HashMap을 만들었으면 이제 값을 저장할 차례이다. value에 계속 값을 더하는 유형이 많이 나오는데 이럴경우 "getOrDefault" 메소드를 이용해서 값이 존재하지 않으면 기본적으로 0을 반환하도록 할 수 있다.

for(String partiPerson : participant){
	map.put(partiPerson, map.getOrDefault(partiPerson,0) + 1);
}

2.4 keySet() 메소드

현재 HashMap 객체가 가지고 있는 keySet 순회

for ( String key : map.keySet() ) {
	answer = key;
}

2.5 정렬

HashMap의 value값을 기준으로 key값들을 정렬해야하는 경우들이 종종 있다. 오름차순 정렬과 내림차순 정렬 방법을 알고있으면 빠르게 접근할 수 있다.

 Map<String,Integer> resultMap = new HashMap<>();
 
 //값 입력...
 
 //keySetList 내림차순 정렬
List<String> keySetList = new ArrayList<>(resultMap.keySet());
Collections.sort(keySetList, (o1, o2) -> (resultMap.get(o2).compareTo(resultMap.get(o1))));

for(String key : keySetList) {
    System.out.println(String.format("Key : %s, Value : %s", key, map.get(key)));
}



// keySetList 오름차순 정렬
Collections.sort(keySetList, (o1, o2) -> (map.get(o1).compareTo(map.get(o2))));

for(String key : keySetList) {
    System.out.println(String.format("Key : %s, Value : %s", key, map.get(key)));
}

value 기준으로 key를 정렬 한다면, key기준으로 정렬하는 방법도 있다.

Map<Integer, String> testMap = new HashMap<Integer, String>();

// Map에 데이터 추가
testMap.put( 1, "apple");
testMap.put( 4, "pineapple");
testMap.put( 2, "orange");
testMap.put( 3, "melon");

// 키로 정렬
Object[] mapkey = testMap.keySet().toArray();
Arrays.sort(mapkey);

// 결과 출력
for (Integer nKey : testMap.keySet()){
    System.out.println(testMap.get(nKey));
}

다음으로는 TreeMap을 이용해서 자동 정렬 예제이다. TreeMap의 사용 방법은 기본적으로 HashMap과 같다. TreeMap은 put 메소드를 사용해 값을 저장하면 자동으로 정렬해서 저장된다. 정렬되는 순서는 숫자 > 알파벳 소문자 > 한글 순이다.

// Map 선언
Map<Integer, String> testMap = new TreeMap<Integer, String>();

// Map에 데이터 저장
testMap.put(1, "apple");
testMap.put(5, "pineapple");
testMap.put(2, "orange");
testMap.put(3, "strawberry");

// 결과 출력
for (Integer nKey : testMap.keySet()){
    System.out.println(testMap.get(nKey));
}

결과값 출력

apple
orange
strawberry
melon