[알고리즘] 베스트앨범 (프로그래머스 3레벨)

 

 

문제

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

 

풀이

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

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
    	// <장르, 곡 재생횟수 리스트>
        Map<String, List<Integer>> map = new HashMap<>();
        
        for(int i=0; i<genres.length; i++) {
        	if(map.containsKey(genres[i])) {
        		map.get(genres[i]).add(plays[i]); // 리스트에 값 추가
        		continue;
        	}

        	// map에 해당 장르가 없는 경우 
        	map.put(genres[i], new ArrayList<>()); // value 값에 리스트 생성
        	map.get(genres[i]).add(plays[i]);  // 리스트에 값 추가
        }
        
        // 정답 배열 길이
        int arrLength = 0;
        
        // 정답 배열의 길이를 구하는 로직 : 한 장르에 곡 개수가 2개 이상일 때는 +2, 1개일 때는 +1
        for(String key : map.keySet()) {
        	if(map.get(key).size()>=2) {
        		arrLength+=2;
        		continue;
        	}
        	arrLength++;
        }

        // 정답 배열
        int[] arr = new int[arrLength];
        
        List<String> keySetList = new ArrayList<>(map.keySet());

        // key 값을 value 값 기준으로 내림차순으로 정렬
        keySetList.sort(
                (s1, s2) -> sumOfLists(map.get(s2)) - sumOfLists(map.get(s1))
                );

        
        int idx = 0; // 정답 배열의 idx 값
        
        for(String key : keySetList) {
            
        	/**
        	 * 한 장르에 곡 개수가 2개 이상인 경우
        	 */
        	if(map.get(key).size()>=2) {
        		
        		int temp = idx;  // idx 값을 잠시 보관할 값
        		
        		// 값이 채워졌는지 안채워졌는지 확인
        		boolean checkOne = false;
        		boolean checkTwo = false;
        		
        		// map의 key 값의 value 리스트의 내림차순 정렬 
        		Collections.sort(map.get(key), Collections.reverseOrder());
                
            	for(int i=0; i<genres.length; i++) {
                    
            		// 한 장르당 재생 리스트가 많은 2개의 곡이 모두 채워졌을 경우 break
            		if(checkOne && checkTwo) break;

            		if(key.equals(genres[i]) // key 값과 장르가 일치해야 한다.
            				&& map.get(key).get(0) == plays[i]  // 장르 내 재생 수가 가장 많은 리스트의 곡이다.
            						&& !checkOne) {  // 값이 아직 안채워져야 한다.
            			
            			arr[temp] = i;  // arr의 temp 값에 i 번쨰 값을 넣는다.
            			checkOne = true;  // 값이 채워졌으므로 true
            			continue;
            		}
            		
            		if(key.equals(genres[i]) // key 값과 장르가 일치해야 한다.
            				&& map.get(key).get(1) == plays[i] // 장르 내 재생 수가 2번째로 많은 리스트의 곡이다. 
            						&& !checkTwo) { // 값이 아직 안채워져야 한다.
            			
            			arr[temp+1] = i;  // arr의 temp+1 값에 i번째 값을 넣는다.
            			checkTwo = true;  // 값이 채워졌으므로 true
            		}
            	}
            	
            	idx +=2;  // 2개의 값을 채웠으므로 idx 값을 +2 한다.
        		continue;
        	}
        	
        	/**
        	 * 한 장르에 곡 개수가 1개인 경우
        	 */
        	for(int i=0; i<genres.length; i++) {
        		if(key==genres[i]) {  // 장르만 일치하면 된다.
        			arr[idx++] = i;
        		}
        	}
        	
        }  // end for key
        
        return arr;
    }
    
    // 리스트의 합을 구하는 메서드
    static int sumOfLists(List<Integer> list) {
    	return list.stream().mapToInt(Integer::intValue).sum();
    }
    
}