아직도 이직을 준비하고 시험을 치르는 기업들이 많다. 알고리즘 테스트를 준비하기 위해 알고리즘을 다시 다루기 시작했습니다.
https://school.programmers.co.kr/learn/courses/30/lessons/42579
프로그램 제작자
코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
Programmer.co.kr
대상 문제의 경우 Programmer’s Highscore Kit의 해시 문제 중 하나..!
문제 설명
하나의 스트리밍 사이트에서 각 장르별로 가장 많이 재생된 두 곡을 모아 베스트 앨범을 발매하려고 합니다. 곡은 고유 번호로 분류되며, 곡을 녹음하는 기준은 다음과 같습니다.
- 가장 많이 재생된 곡이 있는 장르가 먼저 포함됩니다.
- 장르 내에서 가장 많이 재생된 노래가 먼저 나열됩니다.
- 장르 내 재생 횟수가 같은 곡 중에서 고유 번호가 낮은 곡이 먼저 나열됩니다.
노래의 장르를 나타내는 문자열 배열 장르와 노래당 재생 횟수를 나타내는 정수 배열 재생이 주어지면 포함된 고유한 노래 수를 최고의 앨범 순서대로 반환하는 해결 함수를 완료합니다.
제한
- 장르(i)는 고유 번호 i가 있는 노래의 장르입니다.
- play(i)는 고유 번호 i가 있는 노래가 재생된 횟수입니다.
- 장르와 트랙의 길이는 동일하며 범위는 1에서 10,000입니다.
- 100개 미만의 장르 유형이 있습니다.
- 한 장르에 한 곡만 있는 경우 한 곡만 선택합니다.
- 각 장르마다 곡 수가 다릅니다.
I/O 예시
장르 조각 반환
| (“클래식”, “팝”, “클래식”, “클래식”, “팝”) | (500, 600, 150, 800, 2500) | (4, 1, 3, 0) |
I/O 예시 설명
클래식 장르는 1,450회 재생되었으며 클래식 곡은 다음과 같습니다.
- 고유 번호 3: 800 게임
- 고유 번호 0: 500 게임
- 고유 번호 2: 150 게임
팝 장르는 3,100회 재생되었으며 팝송에는 다음이 포함됩니다.
- 고유 번호 4: 2,500 게임
- 고유 번호 1: 600 게임
따라서, 팝 장르의 곡(4, 1)이 먼저 녹음되고, 클래식 장르의 곡(3, 0)이 다음에 녹음된다.
- 2위는 장르별로 가장 많이 재생된 곡을 2곡까지 모아 베스트 앨범을 발매하기 때문에 포함하지 않습니다.
나는 먼저 문제를 풀기 위해 생각을 정리했다.
- 어떤 정보가 필요합니까?
- 장르 중에서 많이 플레이한 장르(#1, #2)를 찾아야 합니다.
- 선택한 장르 내에서 가장 많이 재생된 곡의 순서대로 답을 입력하십시오.
- 장르에 포함된 노래가 2곡 미만인 경우 1곡만 베스트 앨범에 포함될 수 있습니다.
- 재생 횟수가 같으면 고유 번호가 낮은 앨범이 베스트 앨범이 됩니다.
- 더 쉽게 사용할 수 있도록 제공된 정보에 어떻게 액세스해야 합니까?
- 고유번호, 재생횟수, 장르를 앨범에 넣고 관리하자!
위의 코드를 정리한 후 다음 코드가 생성되었습니다.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class 베스트앨범 {
static class Album {
//고유번호
int id;
//재생수
int playCount;
//장르
String genre;
int totalPlay;
public Album(int id, int playCount, String genre) {
this.id = id;
this.playCount = playCount;
this.genre = genre;
}
public Album(int totalPlay) {
this.totalPlay = totalPlay;
}
@Override
public String toString() {
return "Album{" +
"id=" + id +
", playCount=" + playCount +
", genre="" + genre + "\\'' +
", totalPlay=" + totalPlay +
'}';
}
}
public static void main(String() args) {
String() genres = {"classic", "pop", "classic", "classic", "pop"};
int() plays = {500, 600, 150, 800, 2500};
// String() genres = {"classic", "classic", "classic", "pop"};
// int() plays = {500, 150, 800, 2500};
// String() genres = {"classic", "classic", "classic", "classic"};
// int() plays = {500, 400, 300, 200, 100};
//사용하기 쉬운 형태로 데이터를 가공한다.
Map<String, List<Album>> map = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
if (map.get(genres(i)) == null) {
List<Album> list = new ArrayList<>();
Album album = new Album(i, plays(i), genres(i));
//장르별 리스트 저장
list.add(album);
map.put(genres(i), list);
} else {
List<Album> list = map.get(genres(i));
Album album = new Album(i, plays(i), genres(i));
list.add(album);
}
}
System.out.println("map = " + map);
//리스트내 순서 정렬
for (String key : map.keySet()) {
List<Album> list = map.get(key);
list.sort((o1, o2) -> {
//1번조건 노레카운트가 높은순서, 노래카운트가 같다면 고유번호(id)가 낮은순서
if (o1.playCount > o2.playCount) {
return -1;
} else if (o1.playCount == o2.playCount) {
if (o1.id < o2.id) {
return -1;
} else {
return 1;
}
} else {
return 1;
}
});
}
System.out.println("map = " + map);
//장르별 총 갯수 획득
Map<String, Album> playCountMap = new HashMap<>();
for(int i = 0; i < genres.length; i++) {
int play = plays(i);
String key = genres(i);
int id = i;
if (playCountMap.get(key) == null) {
Album album = new Album(play);
album.genre = key;
playCountMap.put(key, album);
} else {
Album album = playCountMap.get(key);
int totalPlay = album.totalPlay;
album.totalPlay += play;
playCountMap.put(key, album);
}
}
System.out.println("playCountMap = " + playCountMap);
List<Album> countList = new ArrayList<>();
for (String key : playCountMap.keySet()) {
Album album = playCountMap.get(key);
countList.add(album);
}
countList.sort((o1, o2) -> {
if (o1.totalPlay > o2.totalPlay) {
return -1;
} else {
return 1;
}
});
System.out.println("countList = " + countList);
List<Integer> resultList = new ArrayList<>();
for (Album album : countList) {
List<Album> list = map.get(album.genre);
if (list.size() < 2) {
int id = list.get(0).id;
resultList.add(id);
} else {
for (int i = 0; i < 2; i++) {
int id = list.get(i).id;
resultList.add(id);
}
}
}
int() ints = resultList.stream().mapToInt(value -> value).toArray();
System.out.println("ints = " + ints);
}
}
작성된 논리는 다음과 같습니다.
- 사용하기 쉬운 형태로 데이터를 처리합니다.
- 지도를 이용하여 장르별(장르별 분류) 앨범 항목 목록에 정보를 넣었습니다.
- 나중에 쉽게 사용할 수 있도록 미리 정리하십시오.
- 리스트의 내부
미리 정리했습니다. 데이터는 이미 장르별로 수집되어 있기 때문에 playCount 순으로 정렬되며, playCount가 같을 경우 고유번호(statement for 파일에 입력된 i-value)를 기준으로 추후 2 또는 1 정렬 및 찾기 앞에서 1 또는 2를 사용할 수 있습니다.
- 리스트의 내부
- 각 범주의 합계를 구하십시오.
- 어떤 장르를 베스트 앨범의 타깃으로 삼을지 정해야 했기 때문에 몇 번이나 재생되는지 알아야 했고 총 재생 횟수가 많은 두 장르를 타깃으로 삼아야 했다.
- 3번 장르를 기준으로 1번에서 처리한 데이터를 불러와 목록의 크기를 보고, 2곡 이상이면 처음 2번과 1번은 1번의 고유번호를 얻어서 사용!
모든 것이 작성되고 문제가 해결된 후 해시는…? 사용했다고 생각합니까? 의심이 듭니다.