[프로그래머스] 베스트앨범(LV3 - JAVA, Python)

프로그래머쓱

해당 글에서는 베스트앨범 문제를 JAVA와 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

 

🔷 문제 풀이

1️⃣ Python 풀이

문제 자체는 어렵지 않지만, 구현이 복잡해서 레벨3인 문제가 아닐까 싶다.

특히 파이썬에서는 딕셔너리에 대한 정렬을 제공하기 때문에 훨씬 편했다.

 

해당 문제에서는 카테고리를 통해 해시 문제라는 것을 알았기 때문에, 딕셔너리를 활용해야 함을 알 수 있었다.

 

딕셔너리를 다음과 같이 정보를 저장하고자 했다.

• key: genre(string)
• value: [total play, [(play_a, a_idx), (play_b, b_idx), ...]]
  • 첫 번째 원소는 key에 해당하는 장르의 모든 음악의 재생 횟수에 해당한다.
  • 두 번째 원소는 key에 해당하는 모든 음악을 (재생횟수, 인덱스)를 리스트로 저장한 것이다.

위와 같이 딕셔너리를 저장한 후에, 딕셔너리의 value의 첫 번째 원소인 전체 재생 횟수에 대해 내림차순으로 정렬하여, 많이 재생된 장르순으로 정렬하고, 이후 두 번째 원소에 해당하는 모든 음악에 대해 재생횟수를 기준으로 내림차순 정렬하여 각 장르별 많이 재생된 음악을 출력하고자 한다.

 

위 풀이와 같이 Python 코드를 통해 구현하면 아래와 같다.

def solution(genres, plays):
    answer = []
    
    infos = {}
    for i in range(len(genres)):
        genre = genres[i]
        if infos.get(genre): # genre가 존재하는 경우
            infos[genre][0] += plays[i]
            infos[genre][1].append((plays[i], i)) # play와 index 삽입
        else: # genre가 존재하지 않는 경우
            infos[genre] = [plays[i], [(plays[i], i)]]
    
    infos = dict(sorted(infos.items(), key = lambda x:x[1][0], reverse=True))
    for k, v in infos.items():
        play = v[1]
        play.sort(key = lambda x:x[0], reverse=True)
        length = 2 if len(play)>=2 else len(play)
        for i in range(length):
            answer.append(play[i][1])
            
    return answer

 

사실 딕셔너리 정렬 방법에 대해서만 알면 구현 자체는 어렵지 않다.

 

필자는 infos.items()가 딕셔너리의 key, value를 tuple 모양으로 만든다는 것을 간과하고 람다식에서 x:x[1][0]가 아닌 x:x[0]와 같이 정렬을 해서 틀린 답을 출력했었다. 이에 유의하여 풀이하면 정답 처리를 받을 수 있다.

 

2️⃣ JAVA 풀이

사실 풀이 방법은 Python에서와 유사하지만, JAVA로 풀이하려니까 어려움이 있었다.

 

먼저, HashMap을 이용해 Python과 비슷한 방식으로 각 장르별 전체 재생 횟수를 저장한다.

• key: genre(string)
• value: total play
  • 첫 번째 원소는 key에 해당하는 장르의 모든 음악의 재생 횟수에 해당한다.

여기서 파이썬과 같이 딕셔너리를 가장 많이 재생된 장르 순서로 정렬할 수 있으면 좋았겠지만, Java의 HashMap에서는 정렬이 되지 않는다. 이유는 다음과 같다.

🤖 java에서 HashMap을 정렬하는 방법을 알려줘. 정렬이 불가능하다면 이유도 설명해줘.
Java에서 HashMap은 키와 값을 저장하는 자료구조로, 항목의 순서를 보장하지 않습니다. 이는 내부적으로 해시 테이블을 사용하여 효율적으로 데이터를 저장하기 때문입니다. HashMap을 정렬할 수 없는 이유는 다음과 같습니다
- 순서 없음: HashMap은 항목을 해시 기반으로 저장하므로 입력된 순서가 보장되지 않습니다. 따라서 정렬된 형태로 데이터를 유지하는 데 적합하지 않습니다.

 

따라서 불편한 방식으로 정렬을 해야했다.

각 key를 ArrayList에 저장하고, 이후 람다식을 통해 이전에 HashMap에 저장한 각 장르의 전체 재생 횟수인 key를 기반으로 내림차순 정렬 했다.

ArrayList<String> arr = new ArrayList<>();
for(String g:map.keySet()){
    arr.add(g);
}
arr.sort((g1, g2)->map.get(g2)-map.get(g1));

 

이후에는 각 장르의 가장 많이 재생된 음악을 조건에 맞게 2개(혹은 1개) 찾으면 된다.

이에 대한 코드는 하단의 코드와 같다.

ArrayList<Music> music = new ArrayList<>();
for(String g:arr){
    ArrayList<Music> genre_music = new ArrayList<>(); // 장르가 동일한 music list
    for(int i=0; i<genres.length; i++){
        if (genres[i].equals(g)){ // 현재 장르와 동일한 경우
            genre_music.add(new Music(g, plays[i], i));
        }
    }
    genre_music.sort((m1, m2)->m2.play-m1.play); // play 내림차순으로 정렬
    answer.add(genre_music.get(0).idx);
    if(genre_music.size()>1){
        answer.add(genre_music.get(1).idx);
    }
}

 

이에 대한 전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    
    static class Music{
        String genre;
        int play;
        int idx;
        
        public Music(String genre, int play, int idx){
            this.genre = genre;
            this.play = play;
            this.idx = idx;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i=0;i<genres.length;i++){
            map.put(genres[i], map.getOrDefault(genres[i], 0)+plays[i]);
        }
        
        ArrayList<String> arr = new ArrayList<>();
        for(String g:map.keySet()){
            arr.add(g);
        }
        arr.sort((g1, g2)->map.get(g2)-map.get(g1));
        
        ArrayList<Music> music = new ArrayList<>();
        for(String g:arr){
            ArrayList<Music> genre_music = new ArrayList<>(); // 장르가 동일한 music list
            for(int i=0; i<genres.length; i++){
                if (genres[i].equals(g)){ // 현재 장르와 동일한 경우
                    genre_music.add(new Music(g, plays[i], i));
                }
            }
            genre_music.sort((m1, m2)->m2.play-m1.play); // play 내림차순으로 정렬
            answer.add(genre_music.get(0).idx);
            if(genre_music.size()>1){
                answer.add(genre_music.get(1).idx);
            }
        }
        
        // System.out.println(answer);
        return answer.stream().mapToInt(i->i).toArray();
    }
}

---

요즘 취업 준비를 하면서 코딩테스트에서 JAVA만을 요구하는 기업이 꽤 있어, 연습하고자 파이썬과 자바 둘 다 풀이를 하는 시간을 가졌다. 확실히 파이썬으로는 코드가 간단히 구현되는데, JAVA는 구현이 오래 걸린다는 단점이 있는 거 같다.

 

하지만 JAVA에 대한 기본기도 학습하고, 취업 준비도 JAVA 때문에 제약이 생기거나 하지 않고 일석이조인 거 같다!

코딩테스트를 위해 다시 언어를 학습하는 과정이 쉽지는 않지만, 추후 JAVA를 활용하는 능력에도 큰 도움이 될 거라 생각하고 견뎌내보고자 한다☺️