[프로그래머스/Java] 베스트앨범(Hash 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 Hash 문제에 해당하는 베스트앨범을 자바로 풀어보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

 해결을 위해 아래 코드처럼 작성해 보았다. 단순한 방법으로 HashMap을 선언하여, HashMap의 key를 genre 이름으로, value를 해당 장르의 총 재생수로 설정하여, 재생수를 모두 센 후, max값을 찾아 하나씩 삭제하며 처리하는 방식이다. 

여기서 굳이 answer 배열에 바로 추가하지 않고, 먼저 list에 넣은 후 answer 배열로 옮긴 이유는 answer 배열을 처음에 선언하면 크기가 불분명하기 때문이다. 처음에는 크기가 불분명하니, 그냥 최댓값인 (장르의 개수 * 2)로 설정해 두었는데, 잉여 element 때문에  테스트에 통과하지 못하는 문제가 발생하여 수정했다. 

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String find_max_gen(HashMap<String, Integer> gen) {
        String res = "";
        int max = 0;
        
        for (var entry : gen.entrySet()) {
            if (max < entry.getValue()) {
                max = entry.getValue();
                res = entry.getKey();
            }
        }
        return res;
    }
    
    public int[] solution(String[] genres, int[] plays) {
        int len = genres.length;
        HashMap<String, Integer> gen = new HashMap<String, Integer>();
        
        for (int i = 0; i < len; i++) {
            gen.put(genres[i], gen.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        List<Integer> temp_ans = new ArrayList<>();
        while (!gen.isEmpty()) {
            String max_gen = find_max_gen(gen);
            gen.remove(max_gen);
            
            int first = -1, second = -1;
            for (int i = 0; i < len; i++) {
                if (genres[i].equals(max_gen)) {
                    if (first == -1 || plays[first] < plays[i]) {
                        second = first;
                        first = i;
                    } else if (second == -1 || plays[second] < plays[i]) {
                        second = i;
                    }
                }
            }
            
            temp_ans.add(first);            
            if (second != -1) temp_ans.add(second);
        }
        
        int[] answer = new int[temp_ans.size()];
        for (int i = 0; i < temp_ans.size(); i++) {
            answer[i] = temp_ans.get(i);
        }
        return answer;
    }
}

 

 

 

 이렇게 풀이를 하고 보니, 자바의 장점을 하나도 활용하지 못하고, 너무 중구난방의 코드라는 생각이 들었다. 그래서 다른 사람의 풀이를 보고 몇가지 포인트를 잡아 코드를 수정해 보았다.

1. 스트림을 적극 활용하기
2. Comparable을 implement 한 class 활용

 

 프로그래머스 내에서 다른 사람의 풀이를 보니, 가장 처음으로 보인 풀이는 스트림을 이용한 깔끔한 풀이였다. 거의 스트림만을 이용하여 문제를 해결했다고 해도 과언이 아닐 정도의 풀이였는데, 깔끔하고 좋다는 의견과 효율성이나 문제 의도 측면에서는 좋지 않다는 의견이 모두 존재했다. 하지만 지금은 공부하는 단계이고, 나는 C언어를 주로 사용하여 stream 사용에 약한 상황이라, stream과 함께 문제 의도인 해시도 함께 사용하여 코드를 재작성하는 것을 목표로 잡았다. 

 두 번째는 sort를 할 때, loop를 이용해서 하는 것이 아닌 comparable을 implement 한 새로운 클래스를 만들어서, 한 번에 sort 할 수 있도록 하는 것이다. c언어를 사용하다 보니, sort를 직접 구현하는 데에 익숙한데, 자바에서 제공하는 기능으로 sort를 하는 것을 공부하려 이 포인트를 잡았다. 

 위 포인트만 잡고, 최대한 다른 분들의 코드는 참고하지 않고 다시 코드를 작성해보려 했다.

 

 그렇게 작성한 코드는 아래와 같다. 사실, stream만 적극적으로 활용하면 코드를 획기적으로 줄일 수 있지만, 문제의 의도인 hash 사용을 살리면서 스트림을 사용하다 보니, 스트림 사용이 크게 의미가 있지는 않았다. 다른 분이 쓰신 코드에서는 Collectors.groupingBy()를 사용하셔서, 그룹의 sum으로 정렬을 하시고 limit으로 2개만 추출하는 방식을 사용하셨기 때문에, 이런 방법 말고 hash까지 활용한 방식으로 진행하려다 보니 코드가 길어졌다. 다만 앞서 세운 계획대로 stream과 comparable에 대해 더 공부하게 된 것 같아서 만족한다. 

 

import java.util.*;
import java.util.stream.*;

// Comparable을 implement해 sort를 용이하게 함
class Song implements Comparable<Song> {
    int idx;
    int genr_plays;
    int song_plays;
    
    Song(int idx, int genr_plays, int song_plays) {
        this.idx = idx;
        this.genr_plays = genr_plays;
        this.song_plays = song_plays;
    }
    
    @Override
    public int compareTo(Song s) {
        /*
            장르재생: 내림차순
            노래재생: 내림차순
            고유번호: 오름차순
        */
        if (this.genr_plays == s.genr_plays) {
            if (this.song_plays == s.song_plays) {
                return this.idx - s.idx;
            } else return (s.song_plays - this.song_plays);
        } else return (s.genr_plays - this.genr_plays);
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 장르 재생수 count
        HashMap<String, Integer> gen = new HashMap<String, Integer>();
        int num = genres.length;
        for (int i = 0; i < num; i++) {
            gen.put(genres[i], gen.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        // stream 활용하여 Song list 생성
        List<Song> songs = IntStream.range(0, num)
            .mapToObj(i -> new Song(i, gen.get(genres[i]), plays[i]))
            .sorted()
            .collect(Collectors.toList());
        
        // 장르 별로 두 개만 남기기
        int i = 0, count = 0;
        int pre = 0;
        while (i < songs.size()) {
            Song s = songs.get(i++);
            if (pre == s.genr_plays) {
                if (count >= 2) songs.remove(--i);
                else count++;
            } else {
                count = 1;
                pre = s.genr_plays;
            }
        }
        
        // array 형태로 리턴
        return songs.stream()
            .mapToInt(song -> song.idx).toArray(); //idx만 남김
    }
}