해시의 개념
해시는 키:밸리의 자료구조를 갖는 배열
전화번호부처럼 검색창에 이름(키)을 검색 -> 전화번호(밸류)가 나옴
키가 스트링이다
해시맵 함수
HashMap.put("A", true);
라고 입력하면
마치 HashMap["A"] = true;
원래 해시맵함수는 a가 있다는 것을 전제로 하기 때문에
a가 없다면 에러가 발생하는 작업이 필요. 그래서 a가 있다는 것을 확인해야 하는 번거로움이 있는데
이걸 개선하기 위한 것이 겟올 티폴트 함수이다
키가 없을 경우 에러처리를 한 함수내에서 전부해주는 것.
get/ put/ getOrDefault
- String을 기반으로 정보를 기폭하고 관리해야 될 때 (스트링타입을 기준으로 정보를 기록하고 관리하려면 단순배열을 쓸 수 없으니 해시를 쓰자)
1) 완주하지 못한 선수 (선수이름 -> 완주여부)
2) 신고결과 받기 (신고당한 사람 이름)
3) 위장 (옷의 종류가 스트링형태 )
위장
https://school.programmers.co.kr/learn/courses/30/lessons/42578
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
문제 단순화
1) 옷을 종류별로 구분하여 몇 개의 조합이 가능한지 찾아본다
2) 해시를 사용 (각 종류 별로 오싱 몇가지가 존재하는지 셀 수 있고, 그것들로 총 조합을계산할 수 있기 때문에)
<해시 테이블>
종류 - 이름 // (의상)
headgear - yellowhat, green_turban, none // (3)
eyewear - bluesungl, none // (2)
- 입지 않는 경우를 추가 (종유별로 하나씩 입지않아도되니, 입지 않아도 되는 경우(none)를 추가한다.)
- 전체 조합을 계산하고, 아무 것도 입지 않는 경우를 빼 준다.
(n+1)*(m+1) - 1
function solution(clothes) {
let answer = 1;
// cur[1] -> clothes[i][1]을 key로 만들어!
// acc[cur[1]]에 해당하는 값이 없으면 value가 1이 되고, 값이 존재하면 그 값에 1을 더해주면서 점차 누적이 되는 결과를 낳는다.
let closet = clothes.reduce((acc, cur) => {
acc[cur[1]] = acc[cur[1]] ? acc[cur[1]] + 1 : 1;
return acc;
}, {});
for (let key in closet) {
answer *= closet[key] + 1;
}
return answer - 1; // 아무것도 입지 않는 경우
}폰켓몬
- 꼬부기, 피카츄, 이상해씨, 파이리, 피카츄, 꼬부기, 치코리타
여기서 반을 데려갈 수가 있는데,
중복이 되는 포켓몬을 가져가기가 싫다
총 3마리를 가져갈 수가 있음
-> 꼬부기, 피카츄를 제하면 가져가고 싶은 것은 5마리 하지만 이중에서 3마리만 가져갈 수 있음
- 이상해씨, 고라파덕, 고라파덕, 고라파덕, 꼬부기, 이상해씨, 꼬부기
원래 가져갈 수 있는 것은 3마리
이상해씨, 고라파덕2, 꼬부기를 지우면 중복되지 않은 애들은 3마리이므로 안 겹치게 다 가져갈 수 있음
- 꼬렛, 꼬렛, 삐삐, 꼬렛, 꼬렛, 꼬렛, 꼬렛
3마리를 가져갈 수 있지만 중복 없이 가져갈 수 있는 친구는 꼬렛, 삐삐 2마리뿐임.
중복이 싫기 떄문에 2마리만 데려갈 수 있다.
-> 총 가져갈 수 있는 수(n/2)가 중복이 되지 않는 수보다 크다면 걍 중복되지 않는 수의 마리수만 챙겨가면 된다.
-> 중복되지 않는 수보다 가져갈 수 있는 수가 더 작다면 가져갈 수 있는 최대 수만큼 가져감
// 전달받은 포켓몬 리스트(nums)에서 가져갈 수 있는 최대 포켓몬수 n/2
// 전달받은 포켓몬 리스트에서 고유한 종류의 포켓몬이 몇 마리 있는지 계산
// 최대 포켓몬 수 < 중복되지 않는 수 -> 최대 포켓몬 수 반환
// 최대 포켓몬 수 > 중복되지 않는 수 -> 중복되지 않은 수 반환그냥 푼 버전
function solution(nums) {
// 전달받은 포켓몬 리스트(nums)에서 가져갈 수 있는 최대 포켓몬수 n/2
let takenNum = nums.length/2
// 전달받은 포켓몬 리스트에서 고유한 종류의 포켓몬이 몇 마리 있는지 계산
let uniqueNum = 0;
//[3,1,2,3]
let uniqueMap = {}
for (let i = 0; i < nums.length; i++) {
if(!uniqueMap[nums[i]]) {
uniqueMap[nums[i]] = 1; // "3" : 1 / nN=1 , "2" : 1 / nN =2 , "1": 1 / nN =3
uniqueNum += 1
}
}
// 최대 포켓몬 수 < 중복되지 않는 수 -> 최대 포켓몬 수 반환
return uniqueNum < takenNum ? uniqueNum : takenNum
}<>
function solution(nums) {
let takenNum = nums.length/2
let uniqueNum = new Set(nums).size // 중복 제거, 그리고 개수 파악
return uniqueNum < takenNum ? uniqueNum : takenNum
}- set
HashSet은 입력 순서, 순서가 보장되지 않지만 중복값을 걸러내기에 좋다.
데이터가 정렬될 필요도 없이 중복인지 아닌지만 찾기에 좋음
사용법
HashSet<Integer> set1 = new HashSet<Integer>();//HashSet생성
HashSet<Integer> set2 = new HashSet<>();//new에서 타입 파라미터 생략가능
HashSet<Integer> set3 = new HashSet<Integer>(set1);//set1의 모든 값을 가진 HashSet생성
HashSet<Integer> set4 = new HashSet<Integer>(10);//초기 용량(capacity)지정
HashSet<Integer> set5 = new HashSet<Integer>(10, 0.7f);//초기 capacity,load factor지정
HashSet<Integer> set6 = new HashSet<Integer>(Arrays.asList(1,2,3));//초기값 지정
값 추가
HashSet<Integer> set = new HashSet<Integer>();//HashSet생성
set.add(1); //값 추가
set.add(2);
set.add(3);
-> 입력되는 값이 HashSet 내부에 존재하지 않는다면 그 값을 HashSet에 추가하고 true를 반환하고 내부에 값이 존재한다면 false를 반환합니다.
HashSet 값 삭제
HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(1,2,3));//HashSet생성
set.remove(1);//값 1 제거
set.clear();//모든 값 제거
-> value의 값이 HashSet 내부에 존재한다면 그 값을 삭제한 후 true를 반환하고 없다면 false를 반환
HashSet 값 검색
set.contains(1) -> 불린으로 반환
