해시
(Lv. 1) 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845
문제를 최대한 잘잘 읽고 풀어야 했던 것 같다..
우리는 최대한 많은 종류를 뽑고 싶어 하지만
마리수와 종류는 아무런 연관이 없다는 게 중요하다
극단적인 예시로 4마리가 존재하지만 모두 같은 종류일 때 그 종류는 1개가 된다.
그래서 뽑는 수가 최대한으로 뽑을 수 있는 건 맞지만
!!! 어차피 다 다른 종류라면 중복이 존재할 때 Set을 한 값은 위와 같을 거기 떄문에 !!!
function solution(nums) {
// return 하는 것 : 최대한 다양한 "종류!!!"의 폰켓몬을 선택하는 방법
// 1. N/2마리를 뽑을 때 각각이 다른 경우가 최대로 종류가 다르게 뽑는 것
// 뽑아야 하는 마리수 = 최대한 종류가 다르게 뽑는 마리수
const 최대로종류가다르게뽑는마리수 = nums.length / 2
// 2. 하지만 중복이 존재한다면 종류수가 더 적어짐
// ★ 만약 중복이 존재하지 않으면 아래 값은 중복이 없을 때와 동일한 값
const 중복있을때종류수 = Array.from(new Set(nums)).length
// 같은 로직 : const category = [...new Set(nums)] -> nums를 셋으로 바꾼다음 각각을 배열에 넣어주세요
// ★ 여기에서 min을 사용하는 이유
// 어차피 주어진 마리수와 뽑아야 하는 마리수는 중요하지 않음
// 뽑아야하는 종류수가 뽑는마리수보다 적다면 '그 종류만을 뽑아야하기 때문'
// 만약 [3, 3, 3, 3]으로 다 같을 때 뽑아야 하는 건 2마리지만 종류는 1종류이기때문 그렇기에 종류인 1종류
// 우리는 종류수를 반환해야하므로 min
return Math.min(최대로종류가다르게뽑는마리수, 중복있을때종류수)
}(Lv.1) 완주하지 못한 선수
전에는 sort를 통해 앞에서부터 비교를 하여 풀었던 것 같다
그래서 이번에는 어떻게 해야 map을 활용해서 풀 수 있을까 생각을 하다가
정말 고전적으로 Key와 개수에 해당하는 value값을 통해 넣어주기로 했다
여기에서 핵심은 이름을 set해줄 때 당연히 get해서 존재하지 않으니 undefined가 되어 0값이 삽입될거고 그 후에 +1을 통해 1개만 나올 때 1이 되는 것
존재한다면 +1을 통해 2가 될 것임
이제 그 후에 completion을 돌면서 해당하는 이름을 꺼내와서 존재한다면 -1을 해주면서 value값을 변경해준 후에
마지막으로 value값이 0이 아닌 애를 return 하면 됨
function solution(participant, completion) {
const hashMap = new Map();
// 참가자 이름과 등장 횟수를 기록
// ★ 당연히 처음 set해줄 땐 존재하지 않으니 0이 들어가고 +1을 통해 1이 되는 것
// 이미 존재했다면 그 값에 +1을 더해줌
for (const name of participant) {
hashMap.set(name, (hashMap.get(name) || 0) + 1);
};
// 완주한 선수의 이름을 해시맵에서 감소
// 완주한 사람 있다면 -1씩
for (const name of completion) {
hashMap.set(name, hashMap.get(name) - 1);
}
// 값이 0이 아닌 이름을 찾음 (완주하지 못한 선수)
for (const [name, count] of hashMap) {
if (count > 0) {
return name;
}
}
return null; // 이론상 여기에 도달하지 않음
}(Lv.2) 전화번호 목록
배열에서 가장 길이가 짧은 애 찾기
const minLength = Math.min(...phone_book.map(str => str.length));처음 내가 풀었던 풀이..
function solution(phone_book) {
const minLength = Math.min(...phone_book.map(str => str.length));
const hashMap = new Map();
for(const number of phone_book) {
const startNum = number.slice(0, minLength)
hashMap.set(number, startNum)
}
const hashMapValue = [...hashMap.values()]
const removeDup = new Set(hashMapValue)
// 길이가 같지 않다 -> 중복이 있다
// 길이가 같다 -> 중복이 없다
return hashMapValue.length !== removeDup.size ? false : true
}하지만위처럼 풀다보면, 접두사가 아니고 가장 짧은 애가 존재시엔 걔가 접두사로 되어버림
function solution(phone_book) {
// ★ 어떤 번호가 다른 번호의 접두어인 경우가 있을 때! 임
const hashMap = new Map();
// 1. 전화번호를 해시맵에 저장
for (const number of phone_book) {
hashMap.set(number, true);
}
// 2. 접두사 검사
for (const number of phone_book) {
let prefix = "";
// ★ 여기에서 처음이 접두사여도 number.length-1을 통해
// ★ 자기 자신이 has에 걸리지 않도록 함
// ★ 나중엔 어차피 접두사가 포함된 애 돌면서
// ★ 접두사로 쓰인 애가 포함되니
for (let i = 0; i < number.length - 1; i++) {
prefix += number[i]; // 접두사 생성
if (hashMap.has(prefix)) {
return false;
}
}
}
return true;
}
위처럼 hashMap을 통해서 넣어주되, 가장 큰 핵심은 자기 자신이 포함되지 않고 후반에는 검사할 수 있도록 length - 1을 해주는 것
다른 사람의 풀이
해시를 사용해서 풀진 않았지만 startWiths 푼 것이 인상적
function solution(phoneBook) {
return !phoneBook.sort().some((t,i)=> {
if(i === phoneBook.length -1) return false;
return phoneBook[i+1].startsWith(phoneBook[i]);
})
}
(Lv.2) 의상
hashMap의 value들로 배열을 만들려면
const hashMapList = [...hashMap.values()]value는 단독적이므로 배열로 바꾸어 같은 key일 때 이어주기
for(const [cloth, category] of clothes) {
if (!hashMap.has(category)) {
hashMap.set(category, [cloth])
} else {
hashMap.get(category).push(cloth)
}
}처음에 푼 풀이
function solution(clothes) {
const leastClothes = clothes.length;
// 어떻게 됐던 한번씩 옷은 입을 거고 그 다음 여러 개를 가진 값을 찾아서 곱해주는 경우의 수를 찾으면 됨
const hashMap = new Map();
let ans = 0;
for(const [cloth, category] of clothes) {
if (!hashMap.has(category)) {
hashMap.set(category, [cloth])
} else {
hashMap.get(category).push(cloth)
}
}
const hashMapList = [...hashMap.values()]
console.log(hashMapList.length)
console.log('@',leastClothes)
return hashMapList.length === 1 ? leastClothes : leastClothes + hashMapList.reduce( (a,c) => a*c.length, 1)
}경우의수를 따지자면 이렇게 되지만 내가 간과한 게 하나 있었다.
해당 카테고리의 옷을 "착용하지 않을 때의 경우이다
그러므로 각 카테고리에서 아무것도 입지 않을 경우의 수를 + 1을 통해 더해주고
마지막 정답값 -1을 통해 아무런 것도 입고 나가지 않았을 때의 경우를 뺴주면 됨
function solution(clothes) {
const leastClothes = clothes.length;
// 어떻게 됐던 한번씩 옷은 입을 거고 그 다음 여러 개를 가진 값을 찾아서 곱해주는 경우의 수를 찾으면 됨
const hashMap = new Map();
let ans = 0;
for(const [cloth, category] of clothes) {
if (!hashMap.has(category)) {
hashMap.set(category, [cloth])
} else {
hashMap.get(category).push(cloth)
}
}
const hashMapList = [...hashMap.values()]
// length + 1은 아무 것도 착용하지 않을 때에 경우의 수
// - 1 아무것도 입지 않는 경우 제외
return hashMapList.reduce((acc, cur) => acc * (cur.length + 1), 1) - 1;
}다른 사람의 풀이
map보다는 object를 썼지만 그래도 유의미한 풀이인 것 같다
function solution(clothes) {
let answer = 1;
const obj = {};
for(let arr of clothes) {
obj[arr[1]] = (obj[arr[1]] || 0) + 1;
}
for(let key in obj) {
answer *= (obj[key]+1);
}
return answer - 1;
}
정말 단순하게 각 object에 수를 바로 넣어준 다음 (존재 안 하면 1, 존재할 땐 +1씩 더해주기)
그러다가 하나 씩 빼서 안 입는 경우까지 곱해주며 계산한 후에 아무것도 안 입을 때의 경우를 뺴주는 방법!
깔끔한 것 같다
(Lv.3) 베스트 앨범
무려 한 이틀정도 걸린 문제,
처음에 짠 로직으로 TC 2, 15빼고 다 통과 였는데 그래서 조금만 고치면 되려나 싶었지만 그게 아니라 내가 상세조건 중 한 개인
고유번호가 낮은 노래를 먼저 삽입한다는 기준을 무시했기 떄문에 답이 될 수 없는 코드였다
function solution(genres, plays) {
// ★ 고유 번호는 각 노래가 가져야 하는 값임
const hashMap = new Map();
const sumHashMap = new Map();
const album = [];
for(let i=0; i<genres.length; i++) {
album.push([genres[i], plays[i], i])
}
for (const [genre, play, index] of album) {
// 1. 인덱스와 함께 넣어주기
if (!hashMap.has(genre)) {
hashMap.set(genre, [[index, play]]);
} else {
hashMap.get(genre).push([index, play]);
}
// 장르에 해당하는 value가 존재하면 그 값에 + play를 더해주고 아니면 0에다가 play를 더해줌
const totalPlays = (sumHashMap.get(genre) || 0) + play;
sumHashMap.set(genre, totalPlays);
}
// entries() => Map객체를 Array로 반환 [ ['키', 'value'], ['키', 'value']]
console.log('[...sumHashMap.entries()]', [...sumHashMap.entries()])
// totalPlays에 따른 내림차순 적용
const sortedKeys = [...sumHashMap.entries()].sort((a, b) => b[1] - a[1]) // value 기준 내림차순 정렬
.map(entry => entry[0]);
// key 값만 추출
// 출력: ['pop', 'classic']
const ans = [];
sortedKeys.forEach( (value) => {
const hashMapValue = hashMap.get(value)
// 재생횟수를 먼저 sorting 한 후에
// (비교는 크냐, 작냐 둘이니까 근데 그게 ||를 타는 false일 땐 두 값이 같은 경우임)
// -> 그러므로 만약 동일 하다면 그 다음 유효번호로 sorting
hashMapValue.sort((a, b) => b[1] - a[1] || a[0] - b[0])
// 고유번호 삽입
ans.push(...hashMapValue.slice(0, 2).map(value => value[0]))
})
console.log('넣어진 ans',ans)
return ans
}나는 남들과는 다르게 먼저
-
for문을 써서 인덱스를 넣어도 되지만 난 album이라는 배열을 만든 후 for of 를 사용해서 해당 값들을 넣어주었다
-
그 후 각 노래와 index값도 넣어주고 totalPlays를 sumHashMap이란 배열에 넣어주는데
여기에서 한 가지 집중할 점은
(sumHashMap.get(genre) || 0) + play다.
value값을 꺼내고 그 값이 존재한다면 계속해서 play를 더해주고 그게 아니라면 0에다가 더해주는 방식!
★ 또한 entries() 라는 메서드를 통해 Map객체를 Array로 반환하면 된다
['키', 'value']
-
이렇게 변환된 Map을 통해 내림차순 적용으로 어떤 애가 play횟수가 더 많은지 따져서 그 장르를 먼저 넣을 것임
-
최종적으로 장르의 반복문을 돌며 장르의 pop에 해당하는 hashMap의 Value를 가져온 후 그 value들을 소팅할 건데
처음에는 재생횟수로 비교한 후 || 를 통해 같다면 유효번호로 소팅한 후
ans배열에 2개씩 짤라 넣어주었다!
