📌 Dictionary Problem
- Question - Direct access table의 문제점과 해당 문제를 해결하는 적절한 hashing 함수를 검색하고 적용하여라
📍 Direct Access Table
-
What is?
Direct Address Table이라고도 불리며 key 값을 주소로 사용한다.
-
Problem
key를 알고 있으면 O(1) 시간 복잡도로 접근할 수 있지만 최대 index - 1만큼의 자원을 낭비할 가능성이 있다.
예를 들어 key-value 쌍이 10-31, 11-56, 1000-137라고 했을 때 table index는 0 ~ 1000로 1001개의 공간이 있다.
하지만 3개의 데이터만 저장한 상태이기 때문에 998개의 공간이 낭비된다. -
Solution
Hashing 함수를 사용하면 이러한 문제를 해결할 수 있다.
가장 간단한 hash 함수는 h(x) = x % N이다. N으로 나눈 나머지를 key 값으로 사용하는 것이다.
위의 예시를 N=10으로 다시 생각해보면 h(31) = 1, h(56) = 6, h(137) = 7이 된다. N=10이기 때문에 배열의 길이는 10으로 제한할 수 있다.
📍 Implement
class Hash {
private final int SIZE;
private final int[] arr;
public Hash(int size) {
SIZE = size;
arr = new int[SIZE];
}
public int hashKey(int value) {
return value % SIZE;
}
public void add(int value) {
arr[hashKey(value)] = value;
}
}📌 Rabin-Karp Algorithm
- Question - Rabin-Karp algorithm을 구현하고 충분히 심험한 후 결과를 공유하여라
📍 Implement
package report03;
import java.util.ArrayList;
import java.util.List;
public class KarpRabin {
private String string;
public KarpRabin(String string) {
this.string = string;
}
public int hash(String string) {
int sum = 0;
for (int i = 0; i < string.length(); i++) {
sum += ((int) string.charAt(i)) * Math.pow(2, string.length() - 1 - i);
sum %= 10000000;
}
return sum;
}
public List<Integer> find(String string) {
List<Integer> list = new ArrayList<>();
int hash = hash(string);
for (int i = 0; i <= this.string.length() - string.length(); i++) {
String substring = this.string.substring(i, i + string.length());
if (hash == hash(substring))
list.add(i);
}
return list;
}
public String getString(int index, int length) {
return string.substring(index, index + length);
}
}📍 Test
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter string : ");
KarpRabin algorithm = new KarpRabin(sc.next());
System.out.print("Enter string to find : ");
String find = sc.next();
long start = System.currentTimeMillis();
List<Integer> indexes = algorithm.find(find);
long end = System.currentTimeMillis();
System.out.println("Time for search : " + (end - start) + "ms");
for (Integer index : indexes) {
String foundString = algorithm.getString(index, 3);
System.out.println("Index : " + index + " || String : " + foundString + " || Hash : " + algorithm.hash(foundString));
}
}
- 적절하게 찾은 경우
- 적절하게 찾지 못한 경우
- Result
첫 번째 경우를 보면 원하는 값을 모두 찾은 것을 확인할 수 있다.
하지만 두 번째 경우에서는 hoa를 모두 찾기는 했지만 추가로 fsa를 찾은 것을 확인할 수 있다.
이는 서로 다른 문자열이라도 같은 해시값을 가질 수 있기 때문이다.
이를 방지하기 위해서는 hash로 우선 비교하고 일치하면 문자열 전체를 비교하는 연산을 추가하면 된다.
📌 Open-Address & Chaining
- Question - Open address와 Chaining을 설명하고 장단점을 비교하여 설명하여라 Open-Address와 Chaining은 hash collision에 대한 해법이다.
📍 Concept
- Open-Address
Open addressing 기법은 hash 충돌이 발생했을 때 바로 다음 주소에 값을 저장한다.
- Chaining
Chaining 기법은 hash 충돌이 일어났을 때 hash 값을 변경하지 않고 동일한 table 공간에 linked list으로 값을 저장하는 방법이다.
📍 Open-Address vs Chaining
📌 Uniform Hashing
- Question - Multiplication method를 언급하여 uniform hashing을 설명하여라
📌 Programmers
📍 Question 01
import java.util.HashMap;
import java.util.Map;
class Solution {
public String solution(String[] participants, String[] completions) {
Map<String, Integer> map = new HashMap<>();
for (String completion : completions)
if (map.containsKey(completion)) map.put(completion, map.get(completion) + 1);
else map.put(completion, 1);
String failed = "";
for (String participant : participants) {
if (!map.containsKey(participant)) {
failed = participant;
break;
} else if (map.get(participant) != 0) {
map.put(participant, map.get(participant) - 1);
}
else{
failed = participant;
break;
}
}
return failed;
}
}📍 Question 02
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class Solution {
public boolean solution(String[] phoneBook) {
Set<String> set = new HashSet<>(Arrays.asList(phoneBook));
for (String s : phoneBook)
for (int end = 0; end < s.length(); end++)
if (set.contains(s.substring(0, end)))
return false;
return true;
}
}📍 Question 03
import java.util.HashMap;
import java.util.Map;
class Solution {
public int solution(String[][] clothes) {
Map<String, Integer> map = new HashMap<>();
for (String[] clothe : clothes) {
String key = clothe[1];
map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
}
int count = 1;
for (Integer value : map.values()) count *= value + 1;
return count - 1;
}
}📍 Question 04
import java.util.*;
import java.util.stream.IntStream;
class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, Genre> map = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
Music music = new Music(i, plays[i]);
Genre genre = map.getOrDefault(genres[i], new Genre(genres[i]));
genre.addMusic(music);
map.put(genres[i], genre);
}
return map.values().stream()
.sorted(Comparator.reverseOrder())
.flatMapToInt(genre -> {
Queue<Music> musics = genre.musics;
if (musics.size() >= 2) return IntStream.of(musics.poll().idx, musics.poll().idx);
else return IntStream.of(musics.poll().idx);
}).toArray();
}
}
class Genre implements Comparable<Genre> {
String genre;
Queue<Music> musics = new PriorityQueue<>(Comparator.reverseOrder());
int total = 0;
public Genre(String genre) {
this.genre = genre;
}
public void addMusic(Music music) {
musics.add(music);
total += music.play;
}
@Override
public int compareTo(Genre o) {
return total - o.total;
}
}
class Music implements Comparable<Music> {
int idx, play;
public Music(int idx, int play) {
this.idx = idx;
this.play = play;
}
@Override
public int compareTo(Music o) {
return play - o.play;
}
}
Hello, Devs!