적당히를 위한 열심히

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

나의 풀이 (java)

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> result =  new ArrayList();
        // map에 넣기 (장르+재생, 장르별 재생수용)
        Map playCountMap = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            playCountMap.put(genres[i], (int)(playCountMap.get(genres[i])==null ? 0:playCountMap.get(genres[i]))+plays[i]);
        }

        // 정렬(장르별 재생수 합산)
        List<Map.Entry<String,Integer>> entryList = new ArrayList<>(playCountMap.entrySet());
        Collections.sort(entryList, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));


        // 장르별 최대 2곡씩 선택
        for (Map.Entry<String, Integer> song : entryList) {
            int first = 0;
            int firstIndex = 0;
            int second = 0;
            int secondIndex = 0;

            for (int i = 0; i < genres.length; i++) {
                if(genres[i].equals(song.getKey())){
                    if(plays[i] > first){
                        second = first;
                        secondIndex = firstIndex;
                        first = plays[i];
                        firstIndex = i;
                    } else if(plays[i] > second){
                        second = plays[i];
                        secondIndex = i;
                    }
                }
            }
            result.add(firstIndex);
            if(second>0) result.add(secondIndex);
        }

        // arrList->arr
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

풀이 방법

• HashMap을 사용하여 중복 제거 or 키-값별 카운트 가능

다른사람의 풀이 (java)

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
  public class Music implements Comparable<Music>{

    private int played;
    private int id;
    private String genre;

    public Music(String genre, int played, int id) {
      this.genre = genre; 
      this.played = played;
      this.id = id;
    }

    @Override
    public int compareTo(Music other) {
      if(this.played == other.played) return this.id - other.id;
      return other.played - this.played;
    }

    public String getGenre() {return genre;}
  }

  public int[] solution(String[] genres, int[] plays) {
    return IntStream.range(0, genres.length)
    .mapToObj(i -> new Music(genres[i], plays[i], i))
    .collect(Collectors.groupingBy(Music::getGenre))
    .entrySet().stream()
    .sorted((a, b) -> sum(b.getValue()) - sum(a.getValue()))
    .flatMap(x->x.getValue().stream().sorted().limit(2))
    .mapToInt(x->x.id).toArray();
  }

  private int sum(List<Music> value) {
    int answer = 0;
    for (Music music : value) {
      answer+=music.played;
    }
    return answer;
  }
}

Godd Idea : 다른사람 : class 나누고, Stream 활용

느낀점

• Comparator 대신 lamda사용
• arrayList<Integer> → array<int>
  => result.stream().mapToInt(Integer::intValue).toArray();

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

나의 풀이

    /* 힌트보고 재작성 */
    public static String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String,Integer> participantMap = new HashMap<>();
        
        for (String partName : participant) {
            participantMap.put(partName, participantMap.getOrDefault(partName, 0)+1);
        }
        
        for (String compName : completion) {
            participantMap.put(compName, participantMap.get(compName)-1);
        }

        for(String name : participantMap.keySet()){
            if(participantMap.get(name) == 1){
                answer = name;
            }
        }
        System.out.println("###  answer : "+answer);
        return answer;
    }

    /* ArrayList를 활용 -> 라인은 줄었지만, 성능에서 또 걸림 */
    public static String solutionSecond(String[] participant, String[] completion) {
        String answer = "";
        List<String> participantList = new ArrayList<>();
        for (String person : participant) {
            participantList.add(person);
        }
        for (String comp : completion) {
            participantList.remove(comp);
        }
        answer=participantList.get(0);
        System.out.println("###  answer : "+answer);
        return answer;
    }

접근 방법

처음에 중첩 loop를 사용해서 하나씩 제거하는 방법을 생각했지만, 시간이 오래걸려서 채점에서 CUT
힌트를 보고서야 이 문제가 해시를 이용한 문제라는걸 알았다...
처음엔 Hash Set 을 이용했지만, 중복이 없어지는 Hash의 특성으로 계속 막혀서 결국 힌트를 봤다.

다른 사람의 풀이를 슬쩍 봤는데, 성능을 위해 해시를 쓰되, 중복처리를 위해 맵을 이용해 count를 하는게 인상깊었다

다른 사람의 풀이

HashMap 사용

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

Sorting 사용

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for ( i=0; i<completion.length; i++){

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[i];
    }
}

비록 해시 문제이지만,  개인적으론 풀이법은 아래가 좀 더 멋져보인다

느낀점

일단, 어떤 문제든 일단 중첩 loop로 접근하는 나를 보며, 아쉬웠다

이번에 적절한 자료구조를 찾는게 힘들었다. Hash 까지는 문제를 보며 찾아갔지만, 풀이를 보고서야 HashMap을 쓰는 이유를 알게 되다니..

성능을 위해서 Hash를 사용했고

중복 체크를 위해 Map을 사용했다 

getOrDefault() : map에서 get을 하되 없을때 default 값 지정가능

그외의 방법으로는 Array로도 Sorting을 사용하면 시간안에 해결이 가능했지만,

해시에 집착하다보니 Sorting을 더 생각해보지 못해 아쉽다

여러개의 목록에서 중복/여부 체크시 -> Array라면 Sorting 해서 접근하는 방법도 좋을듯하다

비슷한 유형

[프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
[프로그래머스] 전화번호 목록 (해시 Lv. 2)
[프로그래머스] 위장 (해시 Lv. 2)
[프로그래머스] 베스트 앨범 (해시 Lv. 3)