Younho9 NotesProgrammers 42579. 베스트 앨범
Title
Programmers 42579. 베스트 앨범
Category
AlgorithmTags
Aliases
Programmers 42579. 베스트 앨범Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 해시 | lv.3 | 1시간 | ✅ |
설계 방법
genres를 순회하면서,genres와plays의index가 같으므로, 장르별로first,second,sum을 기록한hashMap을 구성한다.hashMap의values를sum을 기준으로 정렬한 이후, 순회하며 장르별first,second로 앨범을 구성한다.
코드
javascript
function solution(genres, plays) {
const hashMap = genres.reduce((hash, genre, i) => {
if (hash.has(genre)) {
const info = hash.get(genre);
if (plays[info.first] < plays[i]) {
info.second = info.first;
info.first = i;
} else if (info.second === null || plays[info.second] < plays[i]) {
info.second = i;
}
info.sum += plays[i];
} else {
hash.set(genre, {
first: i,
second: null,
sum: plays[i],
});
}
return hash;
}, new Map());
return [...hashMap.values()]
.sort((a, b) => b.sum - a.sum)
.reduce(
(album, genre) =>
genre.second === null
? [...album, genre.first]
: [...album, genre.first, genre.second],
[],
);
}
function solution(genres, plays) {
const hashMap = genres.reduce((hash, genre, i) => {
if (hash.has(genre)) {
const info = hash.get(genre);
if (plays[info.first] < plays[i]) {
info.second = info.first;
info.first = i;
} else if (info.second === null || plays[info.second] < plays[i]) {
info.second = i;
}
info.sum += plays[i];
} else {
hash.set(genre, {
first: i,
second: null,
sum: plays[i],
});
}
return hash;
}, new Map());
return [...hashMap.values()]
.sort((a, b) => b.sum - a.sum)
.reduce(
(album, genre) =>
genre.second === null
? [...album, genre.first]
: [...album, genre.first, genre.second],
[],
);
}
시간 복잡도
hashMap 구성 : O(N)
hashMap 정렬 : O(NlogN)
hashMap 순회: O(N)
어려웠던 점
장르별
second가 없을 수 있다는 점에 대한 예외 처리hashMap의value가 객체일 때 가독성이 떨어지는 느낌 ex)hash.get(genre).first