Hash 관련 프로그래머스 문제들을 풀면서 JAVA의 Hash 함수에 대해 정리해보고자 한다.
1. 완주하지 못한 선수
Hash 함수 사용 방법
- HashMap 선언
- put(key, value) - 항목 삽입(key이 중복되는 경우 나중에 삽입된 값이 반영됨)
- get(key) - key에 해당하는 value 값 가져오기
- keySet() - 모든 key 값 가져오기
- getOrDefault(key, default) - key에 해당하는 값이 없는 경우 default 반환
HashMap <String, Integer> map = new HashMap<String, Integer>(); // 해시 함수 선언
map.put("number", 1); // key="number", value=1인 항목 삽입
// key가 "number"인 value값에 1을 더한 값을 key가 "number"인 항목에 삽입
// 이미 key가 "number"인 항목이 있으므로 해당 항목의 value 값을 변경
// 코드 상 key="number", value=2가 됨
map.put(name, map.get("number")+1);
// getOrDefault(key, default)는 HashMap 안에 key와 일치하는 항목이 없는 경우 default 값을 반환
// 일치하는 항목이 있으면 key에 해당하는 value 반환
// 코드 상 key="number", value=3이 됨
// HashMap 선언 후 바로 실행 시 key="number", value=1이 됨
map.put("number", map.getOrDefault("number", 0)+1);
map.get("number"); // key="number"에 해당하는 value 값 가져옴
map.keySet() // map의 key 값들을 모두 가져옴(주의! 배열과 다름. 배열로 선언한 변수에 저장 안됨)완주하지 못한 선수 - 문제 풀이 코드
import java.util.HashMap;
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap <String, Integer> map = new HashMap<String, Integer>();
for(String name:participant) {
map.put(name, map.getOrDefault(name, 0)+1);
}
for(String name:completion) {
map.put(name, map.get(name)-1);
}
for(String key:map.keySet()) {
if(map.get(key) != 0)
answer = key;
}
return answer;
}2. 전화번호 목록
startsWith와 endsWith
- 문자의 처음과 끝이 해당 문자열로 시작, 끝나는지 확인
- 맞으면 true, 아니면 false 반환
- 전화번호 목록 문제를 이 함수 사용하여 풀면 시간 초과 발생
String s= "전화번호 목록";
startsWithT.startsWith("전화"); // true
startsWithT.startsWith("전"); // ture
startsWithT.startsWith(" 전"); // false
hash의 key 포함 여부 확인
- containsKey(s) - 변수 s와 같은 key 값을 가진 항목이 존재 하는지 확인
- 맞으면 true, 아니면 false 반환
전화번호 목록 - 문제풀이 코드
import java.util.HashMap;
public boolean solution(String[] phone_book) {
HashMap <String, Integer> book = new HashMap<>();
for(int i=0; i<phone_book.length; i++) {
book.put(phone_book[i], i);
}
// phone_book 안의 번호들의 앞부분을 잘랐을 때, book map 안에 해당 번호가 있는지 확인하는 for 문
for(int i=0; i<phone_book.length; i++) {
for(int j=1; j<phone_book[i].length(); j++) {
// 즉, 1192라는 번호가 있을 경우 한 자리씩 잘라서 있는지 확인
// ex) j=3 일때, 119라는 번호가 hashmap 안에 있으면 접두어 존재로 false 반ghks
if(book.containsKey(phone_book[i].substring(0, j)))
return false;
}
}
return true;
}3. 위장
생각의 전환 필요
- 3가지의 옷의 종류가 있고, 옷 종류별로 각 n, m, s개의 옷이 있다 가정 했을 때,
(n+m+s)+(nxm+nxs+mxs)+(nxmxs) = (n+1)x(m+1)x(s+1)-1 - 왼쪽의 식을 코드로 작성하면 복잡해지나 오른쪽 식을 코드로 작성하면 간단함.
- 오른쪽 식의 경우 해당 종류의 옷을 안 입는 경우를 각 옷 종류마다 더해주고, 마지막에 아무것도 안 입는 경우를 제외 시켜주는 것
위장 - 문제풀이 코드
import java.util.HashMap;
public int solution(String[][] clothes) {
int answer = 1;
HashMap <String, Integer> clothes_count = new HashMap<>();
for(int i=0; i<clothes.length; i++) {
clothes_count.put(clothes[i][1], clothes_count.getOrDefault(clothes[i][1], 1)+1);
}
for(String key:clothes_count.keySet()) {
answer *= clothes_count.get(key);
}
return answer - 1;
}4. 베스트 앨범
Collections.sort()와 compareTo()
- ArrayList와 Collections.sort() 사용하여 HashMap을 value 값 기준으로 오름, 내림 차순 정렬 하여 출력 가능
- Collections.sort(arrayList)만 하면 arrayList를 오름차순으로 정렬 시킴
- Collections.sort(arrayList, (v1, v2) -> (map.get(v1).compareTo(map.get(v2)))); 하면 map의 value 값 기준으로 arrayList를 오름차순 정렬 시킴
- 오름차순 정렬 : (v1, v2) -> v1.compareTo(v2)는 아래와 같이 반환
v1 > v2 일때, 1
v1 = v2 일때, 0
v1 < v2 일때, -1 - 내림차순 정렬 : (v1, v2) -> v2.compareTo(v1)는 반환된 값이 1(true)일 경우에만 sort 시키기 때문에 내림차순으로 정렬됨
HashMap <String, Integer> map = new HashMap<>();
ArrayList <String> map_asc = new ArrayList<>(map.keySet());
ArrayList <String> map_desc = new ArrayList<>(map.keySet());
// 오름차순 정렬
Collections.sort(map_asc, (v1, v2) -> (map.get(v1).compareTo(map.get(v2))));
// 내림차순 정렬
Collections.sort(map_desc, (v1, v2) -> (map.get(v2).compareTo(map.get(v1))));
// map_asc를 map.keySet() 대신 사용하여 HashMap 항목들을 오름차순으로 출력
for(String key:map_asc) {
System.out.println("key: "+key+", value: "+map.get(key));
}
// map_desc를 map.keySet() 대신 사용하여 HashMap 항목들을 내림차순으로 출력
for(String key:map_desc) {
System.out.println("key: "+key+", value: "+map.get(key));
}베스트 앨범 - 문제풀이 코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public int[] solution(String[] genres, int[] plays) {
int[] answer = {};
HashMap <String, Integer> genres_order = new HashMap<>(); // <장르, 총 재생 횟수>
// 장르 별 총 노래 재생 횟수 카운트
for(int i=0; i<genres.length; i++) {
genres_order.put(genres[i], genres_order.getOrDefault(genres[i], 0)+plays[i]);
}
// 장르 별 총 노래 재생 횟수 내림차순으로 장르 이름 정렬
ArrayList <String> genres_desc = new ArrayList<>(genres_order.keySet());
Collections.sort(genres_desc, (v1, v2) -> (genres_order.get(v2).compareTo(genres_order.get(v1))));
// 내림차순 된 장르들 내 노래들 노래 재생 횟수 내림차순 정렬(재생 횟수 같으면 고유 번호 오름차순)
ArrayList <Integer> result = new ArrayList<>(); // 결과를 담을 ArrayList
for(String g:genres_desc) {
HashMap <Integer, Integer> genres_music = new HashMap<>();
for(int i=0; i<genres.length; i++) {
if(genres[i].equals(g)) {
genres_music.put(i, plays[i]);
}
}
ArrayList <Integer> music_desc = new ArrayList<>(genres_music.keySet());
Collections.sort(music_desc, (v1, v2) -> (genres_music.get(v2).compareTo(genres_music.get(v1))));
result.add(music_desc.get(0));
if(music_desc.size() > 1)
result.add(music_desc.get(1));
}
// 결과 반환
answer = new int[result.size()];
for(int i=0; i<answer.length; i++) {
answer[i] = result.get(i);
}
return answer;
}
I'm job hunting. I want to be a sw developer.