해시 구현
Hash Function : 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수ex) 어떤 숫자를 10으로 나누었을 때 그 나머지를 구하는 함수
public class HashFunction {
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % 90;
}
Java
복사
hash 메소드의 리턴값에서 asciiSum을 size로 나눈 나머지로 설정한 이유는 무엇인가요? Hash Table키와 값이 하나의 쌍으로 이루는 데이터 구조로 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스로 사용하여 데이터와 키를 함께 저장하는 자료구조
public class HashTable {
private int size = 10000;
private int[] table = new int[size];
public HashTable() {
}
public HashTable(int size) {
this.size = size;
this.table = new int[size];
}
public int hash(String key) { // 해시 함수
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % size;
}
public void insert(String key, Integer value) { // key, value 삽입
this.table[hash(key)] = value;
}
public int search(String key) {
return this.table[hash(key)]; // key를 다시 hash로 만들어서 array에서 값을 뽑아 옵니다.
}
Java
복사
테스트 해쉬 자료구조를 왜 사용해야 하나요? 완주하지 못한 선수
풀이 1
접근방식
1.
해쉬맵을 {hashcode(숫자): 선수(문자)} 방식으로 접근
2.
모든 선수들의 합 - 완료한 선수들의 합 = 완료하지못한 선수의 hash값이 남음
3.
참가자 선수 모두의 hashcode를 key값에 둔다. {04103231=선수이름} 느낌
4.
3번을 하면서 key값을 num에 더한다.
5.
완료한 선수들의 hash값을 num에서 뺀다.
6.
완료하지못한 선수의 hash값(key)를 통해 선수(value)를 리턴한다.
import java.util.HashMap;
public class UncompletedPlayer {
public String solution(String[] participant, String[] completion) {
String answer = "";
// 1
HashMap<Integer, String> players = new HashMap<>();
int num = 0;
// 3
for (String player : participant) {
players.put(player.hashCode(), player);
num += player.hashCode();
}
System.out.println(players);
// 4
for (String completed : completion) {
num -= completed.hashCode();
}
// 5
return players.get(num);
}
public static void main(String[] args) {
UncompletedPlayer solution = new UncompletedPlayer();
String[] participant = new String[]{"mislav", "stanko", "mislav", "ana"};
String[] completion = new String[]{"stanko", "ana", "mislav"};
String answer = solution.solution(participant, completion);
System.out.println(answer);
}
}
Java
복사
풀이 2
import java.util.Arrays;
import java.util.HashMap;
public class Solution { // 완주하지 못한 선수
public static void main(String[] args) {
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] participant = {"leo", "kiki", "eden"};
String[] completion = {"eden", "kiki"};
System.out.println(solution(participant, completion));
}
private static String solution(String[] participant, String[] completion) {
String answer = "";
Arrays.sort(participant);
Arrays.sort(completion);
HashMap<String, Integer> map = new HashMap<>();
for (String p : participant) {
map.put(p, map.getOrDefault(p, 0) + 1);
}
for (String p : completion) {
map.put(p, map.get(p) - 1);
}
for (String key : map.keySet()) { // map.keySet()
if(map.get(key) != 0) {
answer = key;
}
}
return answer;
}
}
Java
복사
폰켓몬
풀이 1 - hash 정석
접근방법
1.
hashmap을 {폰켓몬을 나타내는 숫자 : 같은 폰켓몬의 수} 형태를 위해 만든다.
2.
hashmap에 {폰켓몬을 나타내는 숫자 : 같은 폰켓몬의 수}을 넣기 위해 for문을 시행한다.
a.
조건을 파악해서 (총 폰켓몬 수/2)을 넘지 않기 때문에 그에 대한 값 n을 만든다
3.
잡은 폰켓몬들 > n이면, n이 최대값이기에 answer = n
잡은 폰켓몬들 < n 이면 answer = 잡은 폰켓몬들
}
import java.util.HashMap;
public class Solution { // 폰켓몬
public static void main(String[] args) {
// int[] nums = {3,1,2,3};
// int[] nums = {3,3,3,2,2,4};
int[] nums = {3,3,3,2,2,2};
System.out.println(solution(nums));
}
private static int solution(int[] nums) {
int answer = 0;
int n = nums.length/2;
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
hash.put(nums[i], hash.getOrDefault(nums[i], 0)+1);
}
// System.out.println(hash);
if(hash.size() >= n) {
answer = n;
} else {
answer = hash.size();
}
return answer;
}
}
Java
복사
풀이 2 - set활용하기
접근방법
1.
우리가 구하려고 하는건 폰켓몬의 종류임 —> 여러개의 포켓몬이 있더라고 하나의 종류라면 1개로 취급해도 무방하다.
2.
중복을 제거하는 자료구조는 Set의 가장 중요한 특징이다.
3.
잡을 수 있는 최대 개수인 maxCnt를 설정
4.
구하려고하는 것은 포켓몬의 종류를 많이 잡게 하는 것이다. 그래서 min을 활용한다.
a.
종류 > 최대개수 ⇒ 최대개수
b.
종류 < 최대개수 ⇒ 종류
import java.util.HashSet;
import java.util.Set;
public class Ponketmon {
public int solution(int[] nums) {
int maxCnt = nums.length/2;
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int answer = Math.min(maxCnt, set.size());
return answer;
}
}
Java
복사
