자바칩
[프로그래머스 / Java] 코딩테스트 연습: 베스트앨범 (해시) 본문
난이도: Level 3
문제: https://school.programmers.co.kr/learn/courses/30/lessons/42579
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
레벨3라서 어려울 줄 알았는데 생각보다 어렵지 않았다.
그냥 주어진 조건을 따라서 정렬만 잘 하면 되기 때문이다.
오히려 같은 해시 문제의 레벨2 문제를 쩔쩔맸다.
아무래도 나는 문제를 단순하게 생각하는 능력이 부족한 것 같다.
먼저 다음과 같이 고유번호, 장르, 재생횟수가 담긴 Song 클래스를 선언한다.
solution 메서드의 맨 윗줄에 Map들을 다음과 같이 선언한다.
위에서 선언한 맵을 다음과 같이 세팅해준다.
inputCounts의 value는 우선 초기값으로 0으로 하고, 최종 값은 가장 나중에 세팅할 것이다.
위에서 만든 Song 클래스 타입의 TreeSet의 정렬 기준을 다음과 같이 정해준다.
아무래도 이 문제가 레벨3인 이유는 이것 때문이 아닐까 싶다.
Integer.compare(a, b) => 오름차순 정렬
Integer.compare(b, a) => 내림차순 정렬
Integer.compare 메서드를 사용하는 대신에 그냥 - 연산자로 비교해도 되지만, '이펙티브 자바' 책에서 비교할 때에는 박싱된 기본 타입의 compare 메서드를 사용하라는 것을 배웠기에 이렇게 썼다.
박싱된 기본 타입인 Integer끼리 == 연산자로 비교하는 것은 값이 같아도 다르게 나올 수도 있기에 이렇게 쓰라는 것이겠지만, 사실 알고리즘 문제에서는 그냥 기본 타입인 int으로만 비교하기 때문에 Integer.compare 메서드 대신에 - 연산자를 사용하면 아래 코드보다 훨씬 간결해지긴 한다.
즉, 다음과 같이 써도 된다는 말이다.
return Integer.compare(a, b) => return a - b
return Integer.compare(b, a) => return b - a
if (Integer.compare(a, b) == 0) => if (a == b)
위에서 TreeSet의 정렬 기준을 정하고, TreeSet에 노래들을 모두 수록한다.
베스트 앨범의 수록할 노래 개수, 즉 최종 리턴할 answer 배열의 원소 개수를 구해야 한다.
왜냐하면 베스트 앨범에는 장르당 2곡씩만 수록하라고 했지만, 어떤 장르의 노래는 1개밖에 없다면 그 장르는 2곡을 수록할 수 없으므로, 즉 베스트 앨범에 수록할 수 있는 곡이 무조건 장르의 개수 * 2가 된다는 보장은 없으므로 이렇게 수동으로 베스트 앨범에 수록할 총 노래 개수를 구해주는 것이다.
마지막으로, 위에서 크기를 초기화한 answer 배열을 채워주고 리턴을 하면 된다.
드디어 여기에서 가장 처음에 선언했던 inputCounts(베스트 앨범에 수록한 각 장르의 노래 개수) 맵을 사용한다.
현재 노래의 장르로 수록한 노래 개수인 inputCounts의 값이 2가 되거나, 만약 장르의 총 노래 개수가 1개일 경우에는 inputCounts에 들어있는 값고 장르의 총 노래 개수의 값이 같을 경우에는 더이상 해당 장르로 노래 수록을 못하게 한다.
위의 경우에 속하지 않다면 answer 배열에 현재 노래의 고유 번호를 추가하고, inputCounts에 현재 노래의 장르인 키에 속하는 값을 1 증가시킨다.
그리고 answer의 index가 answer의 배열 크기와 같아진다면 더이상 노래 수록을 중단하고 반복문을 탈출한다.
베스트 앨범 answer에 노래를 모두 수록했으므로 최종적으로 answer를 리턴하면 된다.
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
int songCount = plays.length; // 노래의 총 개수
// K: 장르, V: 장르의 총 재생 횟수
Map<String, Integer> genrePlays = new HashMap<>();
// K: 장르, V: 장르의 총 노래 개수
Map<String, Integer> genreCounts = new HashMap<>();
// K: 장르, V: 베스트 앨범에 수록한 노래 개수(최대 2개)
Map<String, Integer> inputCounts = new HashMap<>();
// 모든 노래 탐색
for (int i = 0; i < songCount; i++) {
// 장르의 재생 횟수 추가
genrePlays.put(genres[i], genrePlays.getOrDefault(genres[i], 0) + plays[i]);
// 장르의 노래 개수 추가
genreCounts.put(genres[i], genreCounts.getOrDefault(genres[i], 0) + 1);
// 베스트 앨범에 수록한 노래 개수 추가
inputCounts.put(genres[i], 0);
}
// 정렬 기준을 정한 앨범 선언
Set<Song> album = new TreeSet<>(new Comparator<>() {
public int compare(Song s1, Song s2) {
// 장르의 총 재생 횟수가 같다면
if (Integer.compare(genrePlays.get(s2.genre), genrePlays.get(s1.genre)) == 0) {
// 장르 내에서 재생 횟수가 같은 노래가 있다면
if (Integer.compare(s2.play, s1.play) == 0) {
// 우선순위 3: 고유 번호가 낮은 노래를 수록합니다.
return Integer.compare(s1.id, s2.id);
}
// 우선순위 2: 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
return Integer.compare(s2.play, s1.play);
}
// 우선순위 1: 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
return Integer.compare(genrePlays.get(s2.genre), genrePlays.get(s1.genre));
}
});
// 노래를 수록하는 기준으로 정렬한 앨범에 노래 추가
for (int i = 0; i < songCount; i++) {
album.add(new Song(i, genres[i], plays[i]));
}
int bestSongCount = 0; // 베스트 앨범에 수록할 노래 개수
// 모든 장르 탐색
for (String genre : genreCounts.keySet()) {
// 해당 장르의 노래가 1개라면 해당 장르는 최대 1개만 수록 가능
if (genreCounts.get(genre) == 1) {
bestSongCount += 1; // 베스트 앨범에 수록할 노래 개수 1개 추가
} else { // 그렇지 않다면 해당 장르는 최대 2개 수록 가능
bestSongCount += 2; // 베스트 앨범에 수록할 노래 개수 2개 추가
}
}
int[] answer = new int[bestSongCount]; // 베스트 앨범에 수록할 노래의 고유번호 배열
int index = 0; // 베스트 앨범에 수록할 노래 배열의 index
// 정렬한 앨범에 추가한 모든 노래 탐색
for (Song song : album) {
// 베스트 앨범에 수록할 노래 개수만큼 모두 수록했다면, 노래 수록 중단
if (index == answer.length) {
break;
}
// 해당 노래의 장르를 베스트 앨범에 2곡 수록했거나,
// 베스트 앨범에 수록한 노래 개수가 해당 장르의 총 노래 개수와 같다면 (장르의 노래 개수가 1개일 때)
if (inputCounts.get(song.genre) == 2 ||
inputCounts.get(song.genre) == genreCounts.get(song.genre)) {
continue; // 더 이상 해당 장르는 노래 수록 금지
}
answer[index++] = song.id; // 베스트 앨범에 해당 노래의 고유번호 수록
// 베스트 앨범에 수록한 노래 개수 추가
inputCounts.put(song.genre, inputCounts.getOrDefault(song.genre, 0) + 1);
}
return answer; // 베스트 앨범에 수록한 노래의 고유번호 배열 리턴
}
}
class Song {
int id; // 노래의 고유번호
String genre; // 노래의 장르
int play; // 노래의 재생 횟수
Song(int id, String genre, int play) {
this.id = id;
this.genre = genre;
this.play = play;
}
}
|
cs |
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 / Java] 코딩테스트 연습: 디스크 컨트롤러 (힙) (0) | 2024.08.22 |
|---|---|
| [프로그래머스 / Java] 코딩테스트 연습: H-Index (정렬) (0) | 2024.08.11 |
| [프로그래머스 / Java] 코딩테스트 연습: 가장 큰 수 (정렬) (0) | 2024.08.11 |
| [프로그래머스 / Java] 코딩테스트 연습: 의상 (해시) (0) | 2024.08.08 |
| [프로그래머스 / Java] PCCP 기출문제 2번: 석유 시추 (BFS) (0) | 2024.08.04 |
