설명
프로그래머스의 베스트앨범 문제다. 이전에 파이썬으로 푼 적이 있었지만 자바 코딩테스트를 대비해서 다시 풀어보고 있다.
이전 풀이와 비교해서 정말 극명한 차이점은 파이썬으로만 풀다 보니 동일한 알고리즘을 자바에서는 어떻게 구현해야 할 지 정말 난감했다는 것이다. 주석 포함해도 20 몇 줄 정도밖에 안 되던 풀이가 자바로 구현해보니 40 줄을 넘길 정도로 비대해지고 스트림이나 컬렉션 등 다양한 클래스를 활용해야 하다보니 한 번 풀었던 문제지만 몇 시간이나 걸려서 풀 수 있었다.
풀이
풀이는 이전과 동일하다. 사전 자료형(자바에서는 Map)에 노래들을 집어넣고 정렬한 후 꺼내서 두 개씩 뽑아 담는것이다.
import java.util.*;
import java.util.stream.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
// 해당 장르의 총 재생 횟수를 담기 위한 Map.
Map<String, Integer> playCount = new HashMap<>();
// 해당 장르의 음악 및 각 재생 횟수를 담기 위한 Map.
Map<String, List<Integer[]>> genreMusics = new HashMap<>();
// 결과 반환용 List.
List<Integer> result = new ArrayList<>();
// 노래를 Map에 삽입.
for(int id=0; id < genres.length; id++) {
String currentGenre = genres[id];
// 현재 장르의 노래들을 담는 List를 조회. 없다면 ArrayList로 생성.
List<Integer[]> musics = genreMusics.getOrDefault(currentGenre, new ArrayList<Integer[]>());
// (노래 id, 재생 횟수)로 리스트에 저장 후 다시 Map에 저장.
musics.add(new Integer[]{id, plays[id]});
genreMusics.put(currentGenre, musics);
// 현재 장르의 총 재생 횟수를 갱신.
playCount.put(currentGenre, playCount.getOrDefault(genres[id], 0) + plays[id]);
}
// 총 재생 횟수를 기준으로 정렬.
Map<String, Integer> sortedPlayCount =
// (장르, 재생 횟수)의 entry에 대하여 stream 생성.
playCount.entrySet().stream()
// sorted 메서드를 사용하여 Entry의 comparingByValue 기준으로 정렬.
// 내림차순으로 정렬하기 위해 커스텀 Comparator 사용.
.sorted(Map.Entry.comparingByValue((val1, val2) -> val2.compareTo(val1)))
// collect 메서드에 Collectors의 toMap 메서드로 얻은 Collector 적용.
.collect(Collectors.toMap(Map.Entry::getKey, // produce key
Map.Entry::getValue, // produce value
(e1, e2) -> e1, // merge when collision occurs
LinkedHashMap::new)); // empty map provider
// 총 재생 횟수를 기준으로 정렬된 장르 순서대로 두 곡씩 추출.
for(String genre: sortedPlayCount.keySet()) {
List<Integer[]> musics = genreMusics.get(genre);
// 각 장르의 노래들은 재생 횟수를 기준으로 내림차순 정렬.
// Collections의 sort는 stable하기 때문에 낮은 id 우선 조건 만족.
Collections.sort(musics, (val1, val2) -> val2[1].compareTo(val1[1]));
result.add(musics.get(0)[0]);
// 두 곡 이상 있다면 참조하여 결과에 삽입.
if(musics.size() > 1) result.add(musics.get(1)[0]);
}
// int 배열로 변환하여 반환.
int[] arrayResult = new int[result.size()];
for(int i=0;i<arrayResult.length;i++){
arrayResult[i] = result.get(i);
}
return arrayResult;
}
}후기
Map.getOrDefault
이번 문제를 풀면서 참 많은 걸 알 수 있었는데 우선 Map의 getOrDefault 메서드의 활용이다. 이전에 파이썬에서는 collections 모듈의 defaultdict 클래스를 활용하여 해당 키에 대한 값이 없는 경우 자동으로 값을 생성해주곤 했다.
import collections
def solution(genres, plays):
# 각 장르의 각 노래의 재생 횟수를 담을 사전.
musics = collections.defaultdict(list)
# 사전에 각 장르별 노래의 재생 횟수를 등록.
for index, genre in enumerate(genres):
musics[genre].append((plays[index],
...당연히 자바에는 그런게 없을거라 생각하고 contains로 키의 존재 여부를 파악한 후 값을 생성하거나 조회했다. 그런데 getOrDefault 메서드를 잘 살펴보니 이 역시 기본값을 파라미터로 지정해주면 put 메서드와 조합해서 defaultdict처럼 활용할 수 있다는 것을 알게 되었다.
List<Integer[]> musics = genreMusics.getOrDefault(currentGenre, new ArrayList<Integer[]>());만약 해당 키에 대한 값이 없다면 기본값이 생성되어 put 메서드로 저장될 것이고 값이 있다면 기존에 존재하는 값을 활용할 수 있을 것이다.
Stream.sorted
그 다음으로는 스트림의 sorted, collect 메서드다. Map에서 키와 값을 참조하려면 entrySet 메서드를 활용하여 Set<Map.Entry<K, V>> 타입의 자료구조를 얻을 수 있다.
playCount.entrySet().stream()제너릭스 K, V는 각각 Map의 키와 값의 타입을 의미하며 Entry 객체에는 Map의 키와 값이 각각 한 쌍으로 묶여서 제공된다. 이 Entry 객체들을 담고있는 Set은 Collection 인터페이스에 속하기 때문에 stream 메서드로 스트림 객체를 만들 수 있다.
.sorted(Map.Entry.comparingByValue((val1, val2) -> val2.compareTo(val1)))스트림에는 유명한 filter, map, reduce 등의 메서드 말고도 limit, max, min 등 다양한 메서드가 있는데 sorted 메서드로 스트림의 요소들을 정렬하여 받을 수 있다. 파라미터로 아무것도 지정하지 않으면 natural order에 의해 정렬되지만 별도의 Comparator 인터페이스의 구현체(또는 람다식)를 넘겨서 정렬 방식을 지정할 수도 있다.
Map 자료구조는 기본적으로 키를 기준으로 정렬하기 때문에 해당 장르의 총 재생 횟수, 즉 값으로 정렬하려면 별도의 Comparator를 전달해야 한다. 이를 위해서 Map.Entry 클래스에는 Entry 객체를 정렬하기 위한 여러 Comparator를 정적 메서드로 제공해주고 있다. 그 대표적인 것이 위의 코드에서 활용한 comparingByValue 메서드로 이는 Entry 객체를 값으로 비교하는 Comparator를 제공한다. 역시 내림차순으로 비교해야 하기 때문에 반대로 비교하도록 별도의 Comparator를 파라미터로 전달했다.
Entry 객체를 값으로 비교하는 Comparator는 comparingByValue 메서드로 얻을 수 있었으나 그 값을 비교하는 방법을 세부적으로 정하기 위해 Comparator를 람다 표현식으로 전달한 것이다.
Stream.collect
이렇게 중간 연산을 수행했으면 최종적으로 스트림의 요소들을 마무리 연산해서 실제로 쓸 수 있는 자료구조로 받아야 한다. 그 대표적인 메서드가 collect로 이번에는 요소들을 reduction하는 Collector 객체를 파라미터로 받아야 한다.
위의 Comparator처럼 Collector 객체도 Collectors 클래스에서 정적 메서드로 제공한다. 리스트로 만드는 toList, 집합으로 만드는 toSet 등 다양한 Collector가 제공되는데 현재 필요한 것은 정렬된 Map을 만드는 것이기 때문에 toMap 메서드를 사용해야 한다.
.collect(Collectors.toMap(Map.Entry::getKey, // produce key
Map.Entry::getValue, // produce value
(e1, e2) -> e1, // merge when collision occurs
LinkedHashMap::new)); // empty map provider이 메서드는 복잡해보이지만 4개의 파라미터를 받는 것 뿐이다. 각 파라미터는 다음과 같은 목적을 지닌다.
- keyMapper: Map의 키로 사용할 값을 생성하는 함수(또는 Function 인터페이스)
- valueMapper: Map의 값으로 사용할 값을 생성하는 함수(또는 Function 인터페이스)
- mergeFunction: 중복된 키가 있을 때 호출되는 함수(또는 BinaryOperator 인터페이스)
- mapFactory: 연산 결과들이 삽입될 빈 Map 구현체를 생성하는 함수(또는 Supplier 인터페이스)
즉 위의 코드에서는 컬렉션에 들어있는 Entry 객체들에 대하여 getKey, getValue 메서드로 키와 값을 꺼내서 Map 자료구조를 생성하는 것이다. 이 컬렉션의 Entry 객체들은 위에서 sorted 메서드로 정렬되어 있기 때문에 순서대로 꺼내지며 이 순서를 유지해야 하기 때문에 삽입 순서가 유지되는 LinkedHashMap을 사용하는 것이다.
원래 HashMap에 담겨있던 Entry기 때문에 중복된 키가 발생하지 않지만 메서드에서 요구되는 파라미터기 때문에 중복 처리 함수를 간단하게 (e1, e2) -> e1같은 람다식으로 넘겨주었다.
이렇듯 다양한 Stream 클래스의 메서드를 활용하여 복잡한 자료구조를 정렬할 수 있었다. 유연한 파이썬과는 달리 딱딱한 자바를 경험할 수 있는 부분이었다.
Collections.sort
Arrays.sort와 Collections.sort의 가장 큰 차이점은 정렬이 stable하냐 그렇지 않느냐일 것이다. Collections 클래스의 sort 메서드는 stable하며 Arrays 클래스의 sort 메서드는 그렇지 않다.
Collections 클래스는 참조(reference) 타입을 다뤄야 하기 때문에 전후 순서를 유지(stable)한다. Arrays 클래스는 원시(primitive) 타입을 다루기 때문에 전후 순서를 유지할 필요가 없고 순서를 구분할 수도 없다. [1, 2, 3, 2, 4, 4]를 [1, 2, 2, 3, 4, 4]로 정렬했을 때 어차피 원시 타입은 같은 값을 가지면 완전히 동일한 타입이기 때문에 첫 번째 '2'와 두 번째 '2'의 정렬 이전 순서를 유지할 필요는 없는 것이다.
for(int id=0; id < genres.length; id++) {
...
List<Integer[]> musics = genreMusics.getOrDefault(currentGenre, new ArrayList<Integer[]>());
...문제에서는 한 장르에 동일한 재생 횟수의 음악이 있다면 음악의 id가 더 빠른 음악부터 고르도록 제한하고 있다. 구현 코드에서는 위처럼 장르 별 음악을 List에 삽입할 때 for 반복문으로 음악의 id를 0부터 참조하여 삽입하고 있다.
Collections.sort(musics, (val1, val2) -> val2[1].compareTo(val1[1]));그래서 Collections의 sort 메서드로 stable하게 정렬하면 같은 재생 횟수의 음악을 삽입한 id 순서대로 정렬하여 더 낮은 id의 음악을 먼저 조회할 수 있다. 재생 횟수는 내림차순이어야 하기 때문에 별도의 Comparator를 전달한다.
이렇듯 자바의 다양한 측면을 활용해볼 수 있는, 짜증나지만 좋은 문제였다.
