728x90
| 문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항
입출력 예입출력 예 설명 classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다. |
해시와 정렬이 섞인 문제입니다. 보시다시피 장르 이름이라는 "문자열" 배열이 주어지고 특히 중복되는 문자열을 걸러내야 하는 로직이 있습니다. 이럴 경우 해시를 먼저 떠올립니다. 실제 문제 풀 때 카테고리를 알려주진 않으니까요. ㅎㅎ
개인적으로 이 문제에서는 장르 이름이 2번 이상 저장되면 안된다고 생각합니다. 문자열의 연산은 느릴수밖에 없기 때문에 최소한으로 하는 것이 좋습니다. 특히 이 문제에서는 문자열을 비교하는 로직 자체가 불필요합니다.
이 문제는 사람마다 정말 다양한 코드가 있어서 어떤게 좋은 코드인지 모르겠습니다. 프로그래머스에서 연산 시간 통계를 좀 보여줬으면 좋겠네요. 대략 이 글에서 다룰 코드는 아래 속도로 측정됩니다.
* 전체 코드 보기
더보기
package pojoPrj;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
class Solution {
public static void main(String[] args) {
String[] genres = { "classic", "pop", "classic", "classic", "pop", "dance", "k-pop",
"k-pop", "k-pop" };
int[] plays = { 500, 600, 150, 800, 2500, 1000, 2000, 3000, 500 };
int[] result = solution(genres, plays);
System.out.println(Arrays.toString(result));
}
public static int[] solution(String[] genres, int[] plays) {
// key(장르이름) + value(총조회수 + 노래 조회수, 인덱스 정보)
Map<String, GenresInfo> map = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
// 아직 추가되지 않은 장르는 새로 만들어서 추가해줌
if (!map.containsKey(genres[i])) {
// 새로운 GenresInfo 객체
map.put(genres[i], new GenresInfo(plays[i], new ArrayList<SongInfo>()));
// 현재 순서의 노래 정보 추가
map.get(genres[i]).getSongInfoList().add(new SongInfo(plays[i], i));
// 이미 존재하는 장르의 경우
} else {
// 총 조회수 증가시킴
GenresInfo temp = map.get(genres[i]);
temp.setTotalPlays(temp.getTotalPlays() + plays[i]);
// 노래 정보 추가
temp.getSongInfoList().add(new SongInfo(plays[i], i));
}
}
// 노래 정보 정렬 기준
class SongInfoListSort implements Comparator<SongInfo> {
@Override
public int compare(SongInfo o1, SongInfo o2) {
// 조회수 기준 내림차순 정렬, 같은 경우 인덱스 기준 오름차순 정렬
if (o1.getPlays() < o2.getPlays()
|| (o1.getPlays() == o2.getPlays() && o1.getIndex() > o2.getIndex())) {
return 1;
}
return -1;
}
}
// 장르 정보를 배열로 바꾸면서 동시에 각 장르가 가진 노래 리스트를 조회수로 정렬
GenresInfo[] genresInfoList = new GenresInfo[map.size()];
int k = 0;
for (Entry<String, GenresInfo> e : map.entrySet()) {
genresInfoList[k++] = e.getValue();
// 각 장르안의 노래 리스트 정렬
e.getValue().getSongInfoList().sort(new SongInfoListSort());
}
Arrays.sort(genresInfoList);
// 마지막 작업, 각 장르안의 리스트의 노래 정보에서 최대 2개까지만 인덱스 정보를 가져옴
List<Integer> result = new ArrayList<>();
for (GenresInfo g : genresInfoList) {
List<SongInfo> list = g.getSongInfoList();
int size = list.size();
// 1개일 경우
if (size == 1) {
result.add(list.get(0).getIndex());
// 2개일 경우
} else {
for (int i = 0; i < 2; i++) {
result.add(list.get(i).getIndex());
}
}
}
int resultSize = result.size();
int[] answer = new int[resultSize];
for (int i = 0; i < resultSize; i++) {
answer[i] = result.get(i);
}
return answer;
}
}
/* 장르별 정보 */
class GenresInfo implements Comparable<GenresInfo> {
private int totalPlays; // 총 조회수
private List<SongInfo> songInfoList; // 장르에 속한 노래 정보 리스트
public GenresInfo(int totalPlays, List<SongInfo> songInfo) {
this.totalPlays = totalPlays;
this.songInfoList = songInfo;
}
// 정렬기준
@Override
public int compareTo(GenresInfo o) {
// 총 조회수 내림차순
if (totalPlays < o.totalPlays) {
return 1;
}
return -1;
}
public int getTotalPlays() {
return totalPlays;
}
public void setTotalPlays(int totalPlays) {
this.totalPlays = totalPlays;
}
public List<SongInfo> getSongInfoList() {
return songInfoList;
}
public void setSongInfoList(List<SongInfo> songInfoList) {
this.songInfoList = songInfoList;
}
}
/* 개별 노래 정보 */
class SongInfo {
private int plays; // 조회수
private int index; // 인덱스
public SongInfo(int plays, int index) {
this.plays = plays;
this.index = index;
}
public int getPlays() {
return plays;
}
public int getIndex() {
return index;
}
}
문제의 핵심 과정에서 구해야할 것은 아래와 같습니다.
1. 장르별 총 조회수 합계 - 장르 정렬을 위함
2. 장르에 속한 개별 노래 정보(조회수, 인덱스) - 정렬 후 상위 순서 1~2개 뽑아냄
두 개가 다입니다. 저는 두 가지를 한번에 해결하기 위해 객체를 사용했습니다. 하나의 장르는 하나의 객체를 가지고, 이 객체 안에 총 조회수 합계 정보와 속한 노래 정보 리스트를 가지고 있는 구조입니다. 정렬을 할 때 컬렉션 계열에서 사용할 객체는 Comparator 인터페이스를 구현한 객체를 따로 만들어줘야 하고, 일반 배열을 사용할 객체는 Comparable 인터페이스를 구현해줘야 합니다. 고정된 배열을 사용할 것인지 유동적으로 변하는 리스트가 필요한지 결정해서 적절히 구현해주면 됩니다.
[JAVA/- 라이브러리(API)] - java.lang.Comparable / java.util.Comparator 사용법
* 장르 및 개별 정보를 저장할 클래스(객체)
/* 장르별 정보 */
class GenresInfo implements Comparable<GenresInfo> {
private int totalPlays; // 총 조회수
private List<SongInfo> songInfoList; // 장르에 속한 노래 정보 리스트
public GenresInfo(int totalPlays, List<SongInfo> songInfo) {
this.totalPlays = totalPlays;
this.songInfoList = songInfo;
}
// 정렬기준
@Override
public int compareTo(GenresInfo o) {
// 총 조회수 내림차순
if (totalPlays < o.totalPlays) {
return 1;
}
return -1;
}
public int getTotalPlays() {
return totalPlays;
}
public void setTotalPlays(int totalPlays) {
this.totalPlays = totalPlays;
}
public List<SongInfo> getSongInfoList() {
return songInfoList;
}
public void setSongInfoList(List<SongInfo> songInfoList) {
this.songInfoList = songInfoList;
}
}
/* 개별 노래 정보 */
class SongInfo {
private int plays; // 조회수
private int index; // 인덱스
public SongInfo(int plays, int index) {
this.plays = plays;
this.index = index;
}
public int getPlays() {
return plays;
}
public int getIndex() {
return index;
}
}
중복 문자열을 걸러줘야 하는만큼 HashMap을 사용합니다. 해시맵의 key는 장르 이름으로, value는 위의 장르 저장 객체로 설정합니다. 이렇게 하면 해시맵에 딱 하나의 장르가 생기게 되고 이 장르 안에 모든 정보가 포함되기 때문에 좀 더 편리하게 구조를 잡을 수 있을 것 같습니다.
public int[] solution(String[] genres, int[] plays) {
// key(장르이름) + value(총조회수 + 노래 조회수, 인덱스 정보)
Map<String, GenresInfo> map = new HashMap<>();
그리고 배열의 정보를 이용해 해시맵을 완성시켜줍니다. 순회 한번에 모든 작업을 끝낼 수 있도록 했습니다. 어차피 장르의 모든 조회수 합계를 구하려면 배열을 모두 순회해야하고, 개별 노래정보를 알기 위해서도 마찬가지입니다. 해시맵에 담을 객체인 장르 저장 객체(GenresInfo)에 모든 곡정보까지 다 담기기 때문에 자료구조만 잘 잡으면 한번에 해결할 수 있게 됩니다.
class Solution {
public int[] solution(String[] genres, int[] plays) {
// key(장르이름) + value(총조회수 + 노래 조회수, 인덱스 정보)
Map<String, GenresInfo> map = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
// 아직 추가되지 않은 장르는 새로 만들어서 추가해줌
if (!map.containsKey(genres[i])) {
// 새로운 GenresInfo 객체
map.put(genres[i], new GenresInfo(plays[i], new ArrayList<SongInfo>()));
// 현재 순서의 노래 정보 추가
map.get(genres[i]).getSongInfoList().add(new SongInfo(plays[i], i));
// 이미 존재하는 장르의 경우
} else {
// 총 조회수 증가시킴
GenresInfo temp = map.get(genres[i]);
temp.setTotalPlays(temp.getTotalPlays() + plays[i]);
// 노래 정보 추가
temp.getSongInfoList().add(new SongInfo(plays[i], i));
}
}
이제 "하나의 장르객체 - 총 조회수, 개별노래정보 리스트"가 완성되었으므로 정렬만 잘 해주면 됩니다. 해시맵은 정렬이라는 개념이 없으므로 일단 일반 배열로 꺼내줍니다. 이 때 해시맵은 모두 순회해야하므로 장르객체 안에 있는 개별노래정보 리스트의 정렬도 한번에 수행해줬습니다.
개별 노래 정보는 몇 개가 생길지 알 수 없어 컬렉션 List를 사용했기 때문에 정렬을 하기 위한 Comparator 객체를 하나 만든 뒤 정렬해줍니다. 장르 정보는 map에서 갯수가 확정됐기 때문에 일반 배열을 사용했습니다.
// 노래 정보 정렬 기준
class SongInfoListSort implements Comparator<SongInfo> {
@Override
public int compare(SongInfo o1, SongInfo o2) {
// 조회수 기준 내림차순 정렬, 같은 경우 인덱스 기준 오름차순 정렬
if (o1.getPlays() < o2.getPlays()
|| (o1.getPlays() == o2.getPlays()
&& o1.getIndex() > o2.getIndex())) {
return 1;
}
return -1;
}
}
// 장르 정보를 배열로 바꾸면서 동시에 각 장르가 가진 노래 리스트를 조회수로 정렬
GenresInfo[] genresInfoList = new GenresInfo[map.size()];
int k = 0;
for (Entry<String, GenresInfo> e : map.entrySet()) {
genresInfoList[k++] = e.getValue();
// 각 장르안의 노래 리스트 정렬
e.getValue().getSongInfoList().sort(new SongInfoListSort());
}
여기까지 과정으로 장르 객체 안에 있는 개별 노래 정보들이 모두 정렬됐고, 장르객체도 일반 배열로 바꿔줬습니다. 이제 마지막 작업으로 장르객체를 총조회순으로 정렬한 뒤 각자가 가진 개별 정보 노래 리스트의 상위 1~2개만 순서대로 꺼내서 리스트에 추가해주면 됩니다.
그리고 문제에서 int[] 타입을 리턴하도록 했으므로 최종적으로 일반 배열로 변환한 뒤 리턴해주면 됩니다.
// 마지막 작업, 장르배열 정렬 및 각 장르안의 리스트의 노래 정보에서 최대 2개까지만 인덱스 정보를 가져옴
Arrays.sort(genresInfoList);
List<Integer> result = new ArrayList<>();
for (GenresInfo g : genresInfoList) {
List<SongInfo> list = g.getSongInfoList();
int size = list.size();
// 1개일 경우
if (size == 1) {
result.add(list.get(0).getIndex());
// 2개일 경우
} else {
for (int i = 0; i < 2; i++) {
result.add(list.get(i).getIndex());
}
}
}
int resultSize = result.size();
int[] answer = new int[resultSize];
for (int i = 0; i < resultSize; i++) {
answer[i] = result.get(i);
}
return answer;
}
}
* 전체 코드
package pojoPrj;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
class Solution {
public int[] solution(String[] genres, int[] plays) {
// key(장르이름) + value(총조회수 + 노래 조회수, 인덱스 정보)
Map<String, GenresInfo> map = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
// 아직 추가되지 않은 장르는 새로 만들어서 추가해줌
if (!map.containsKey(genres[i])) {
// 새로운 GenresInfo 객체
map.put(genres[i], new GenresInfo(plays[i], new ArrayList<SongInfo>()));
// 현재 순서의 노래 정보 추가
map.get(genres[i]).getSongInfoList().add(new SongInfo(plays[i], i));
// 이미 존재하는 장르의 경우
} else {
// 총 조회수 증가시킴
GenresInfo temp = map.get(genres[i]);
temp.setTotalPlays(temp.getTotalPlays() + plays[i]);
// 노래 정보 추가
temp.getSongInfoList().add(new SongInfo(plays[i], i));
}
}
// 노래 정보 정렬 기준
class SongInfoListSort implements Comparator<SongInfo> {
@Override
public int compare(SongInfo o1, SongInfo o2) {
// 조회수 기준 내림차순 정렬, 같은 경우 인덱스 기준 오름차순 정렬
if (o1.getPlays() < o2.getPlays()
|| (o1.getPlays() == o2.getPlays()
&& o1.getIndex() > o2.getIndex())) {
return 1;
}
return -1;
}
}
// 장르 정보를 배열로 바꾸면서 동시에 각 장르가 가진 노래 리스트를 조회수로 정렬
GenresInfo[] genresInfoList = new GenresInfo[map.size()];
int k = 0;
for (Entry<String, GenresInfo> e : map.entrySet()) {
genresInfoList[k++] = e.getValue();
// 각 장르안의 노래 리스트 정렬
e.getValue().getSongInfoList().sort(new SongInfoListSort());
}
// 마지막 작업, 장르배열 정렬 및 각 장르안의 리스트의 노래 정보에서 최대 2개까지만 인덱스 정보를 가져옴
Arrays.sort(genresInfoList);
List<Integer> result = new ArrayList<>();
for (GenresInfo g : genresInfoList) {
List<SongInfo> list = g.getSongInfoList();
int size = list.size();
// 1개일 경우
if (size == 1) {
result.add(list.get(0).getIndex());
// 2개일 경우
} else {
for (int i = 0; i < 2; i++) {
result.add(list.get(i).getIndex());
}
}
}
int resultSize = result.size();
int[] answer = new int[resultSize];
for (int i = 0; i < resultSize; i++) {
answer[i] = result.get(i);
}
return answer;
}
}
/* 장르별 정보 */
class GenresInfo implements Comparable<GenresInfo> {
private int totalPlays; // 총 조회수
private List<SongInfo> songInfoList; // 장르에 속한 노래 정보 리스트
public GenresInfo(int totalPlays, List<SongInfo> songInfo) {
this.totalPlays = totalPlays;
this.songInfoList = songInfo;
}
// 정렬기준
@Override
public int compareTo(GenresInfo o) {
// 총 조회수 내림차순
if (totalPlays < o.totalPlays) {
return 1;
}
return -1;
}
public int getTotalPlays() {
return totalPlays;
}
public void setTotalPlays(int totalPlays) {
this.totalPlays = totalPlays;
}
public List<SongInfo> getSongInfoList() {
return songInfoList;
}
public void setSongInfoList(List<SongInfo> songInfoList) {
this.songInfoList = songInfoList;
}
}
/* 개별 노래 정보 */
class SongInfo {
private int plays; // 조회수
private int index; // 인덱스
public SongInfo(int plays, int index) {
this.plays = plays;
this.index = index;
}
public int getPlays() {
return plays;
}
public int getIndex() {
return index;
}
}
정렬에서 람다를 사용한다거나 하는 등으로 조금 축약해 짜면 아래와 같이 작성할 수도 있습니다.
package pojoPrj;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, GenreInfo> map = new HashMap<String, GenreInfo>();
for (int i = 0; i < genres.length; i++) {
SongInfo song = new SongInfo();
song.setIndex(i);
song.setPlays(plays[i]);
GenreInfo genre = map.get(genres[i]);
if (genre == null) {
genre = new GenreInfo();
genre.setSong(new ArrayList<SongInfo>());
map.put(genres[i], genre);
}
genre.setSum(genre.getSum() + plays[i]);
genre.getSong().add(song);
}
List<GenreInfo> genreList = new ArrayList<GenreInfo>();
for (GenreInfo g : map.values()) {
g.getSong().sort((o1, o2) -> o2.getPlays() - o1.getPlays());
genreList.add(g);
}
genreList.sort((o1, o2) -> o2.getSum() - o1.getSum());
List<Integer> answer = new ArrayList<Integer>();
for (int i = 0; i < genreList.size(); i++) {
List<SongInfo> song = genreList.get(i).getSong();
int size = song.size();
answer.add(song.get(0).getIndex());
if (size > 1) {
answer.add(song.get(1).getIndex());
}
}
int size = answer.size();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = answer.get(i);
}
return result;
}
}
class GenreInfo {
private int sum;
private List<SongInfo> song;
public int getSum() {
return sum;
}
public void setSum(int sum) {
this.sum = sum;
}
public List<SongInfo> getSong() {
return song;
}
public void setSong(List<SongInfo> song) {
this.song = song;
}
}
class SongInfo {
private int index;
private int plays;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getPlays() {
return plays;
}
public void setPlays(int plays) {
this.plays = plays;
}
}728x90
'▸알고리즘 문제 풀이' 카테고리의 다른 글
| 프로그래머스_정렬_H-index (JAVA) (0) | 2020.04.16 |
|---|---|
| 프로그래머스_정렬_가장 큰 수 (JAVA) (0) | 2020.04.16 |
| 프로그래머스_해시_위장 (JAVA) (0) | 2020.04.15 |
| 프로그래머스_해시_전화번호 목록 (JAVA) (1) | 2020.04.14 |
| 프로그래머스_해시_완주하지 못한 선수 (JAVA) (4) | 2020.04.14 |
댓글