Typiler

베스트앨범 - 3Level

문제설명

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

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

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

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

풀이

해당 문제는 HashMap 정렬을 이용하여 풀었는데, 생각보다 처리 시간이 많이 나옵니다. 다른 방법이 있는지 조금 더 생각할 필요가 있을것 같습니다.

저는 일단 각 장르의 재생횟수가 많은 것을 기준으로 정렬을 하였고, 해당 장르의 고유번호, 재생횟수를 가지는 Music이라는 객체를 만들어 제가 정의한 정렬기준으로 정렬하여 PriorityQueue 를 이용하여 풀었습니다. 아무래도 이중 루프를 돌다보니 시간이 걸리는 것 같습니다.

import java.util.*;
import java.util.Map.*;

class Solution {
    
    public static class Music implements Comparable<Music>{
        int music_num;
        int plays_cnt;
        
        Music(int a, int b){
            this.music_num = a;
            this.plays_cnt = b;
        }
        
        @Override
        public int compareTo(Music tar){
            // 많이 재생된 것
            if(tar.plays_cnt > this.plays_cnt) return 1;
            if(tar.plays_cnt < this.plays_cnt) return -1;
            // 재생수가 같다면 고유번호가 낮은것
            if(tar.music_num < this.music_num) return 1;
            if(tar.music_num > this.music_num) return -1;
            return 0;
        }
        
    }
    
    public Integer[] solution(String[] genres, int[] plays) {
        
        int len = genres.length;
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        for(int i=0; i<len; i++){
       
            if(map.containsKey(genres[i])){
                map.put(genres[i], map.get(genres[i]) + plays[i]);
            }else{
                map.put(genres[i], plays[i]);
            }
            
        }
        
        // map을 value 기준으로 정렬한다.
		List<Entry<String, Integer>> list_entries = new ArrayList<Entry<String, Integer>>(map.entrySet());

		// 비교함수 Comparator를 사용하여 내림차순으로 정렬
		Collections.sort(list_entries, new Comparator<Entry<String, Integer>>() {
			// compare로 값을 비교
			public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2) {
				// 내림 차순 정렬
				return obj2.getValue().compareTo(obj1.getValue());
			}
		});
        
        
        ArrayList<Integer> alist = new ArrayList<Integer>();
        
        // 내림차순으로 정렬된 내용으로 출력한다.
        for(Entry<String, Integer> entry : list_entries) {
            String key = entry.getKey();
            //System.out.println(key + ":" + map.get(key));
            
            PriorityQueue<Music> pq = new PriorityQueue<Music>();
            for(int i=0; i<len; i++){
                if(key.equals(genres[i])) {
                    pq.add(new Music(i, plays[i]));
                }  
            }
            
            int loop=0;
            while(!pq.isEmpty()){
                if(loop==2) break; // 2개만 필요하기때문에 최대 두번만 돌린다.
                Music now = pq.poll();
                alist.add(now.music_num);
                loop++;
            }
        }
        
        //저장된 ArrayList 변수를 Integer[] 배열로 변환한다.
        Integer[] answer = alist.toArray(new Integer[alist.size()]);
        
        
        return answer;
    }
}

결과

K-번째수

문제설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

풀이

이번 문제는 정렬에 관련된 간단한 Level 1 문제입니다. Array 의 복사, 정렬등에 대한 함수를 알고 있는지 파악하려는 것 같습니다. 기본적인 문제이니 확실히 확인하는 것이 좋을것 같습니다.

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        
        for(int n=0; n<commands.length; n++){
            int i = commands[n][0];
            int j = commands[n][1];
            int k = commands[n][2];
            
            int[] tmp = Arrays.copyOfRange(array, i-1, j);
            Arrays.sort(tmp);
            ret.add(tmp[k-1]);
        }
        
        int[] answer = new int[ret.size()];
        for(int i=0; i<ret.size(); i++){
            answer[i] = ret.get(i);
        }

        return answer;
    }
}

결과

알고리즘 문제를 풀다보면 정렬을 해야하는 경우가 많이 발생합니다. 기본적으로 제공되는 Arrays.sort() 함수가 있지만 이것만으로 문제를 풀기에는 한계가 있습니다. 특히 다중차순을 요하는 문제는 직접 구현하는 것이 빠르고 이해가 쉽습니다.

기본적인 정렬 코드

아래는 오름차순, 내림차순, 다중차순의 기본 정렬 구현 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;


class Node implements Comparable<Node>{
	int a;
	int b;
	
	public Node(int a, int b){
		this.a = a;
		this.b = b;
	}

	@Override
	public int compareTo(Node tar) {
		
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1
		// tar 기준으로 우선순위가 동등하면 0
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1
		
		if(tar.a > this.a) return 1;
		if(tar.a < this.a) return -1;
		
		// 첫 수가 우선쉰위가 도등할때 아래 조건을 따른다.
		if (tar.b < this.b) return 1;
		if (tar.b > this.b) return -1;
		
		return 0;
	}
}

public class Sort_ex01 {

	// 정렬
	// 1. 오름차순 
	// 2. 내림차순 
	// 3. 다중차순

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	
    public static void main(String[] args) throws IOException {

        Integer[] arr = {5,4,5,4,4,5};
        
        //1. 오름차순
        Arrays.sort(arr);
        
        //2. 내림차순
        Arrays.sort(arr, Comparator.reverseOrder());
        
        //3. 다중차순
        Node[] arrNode = new Node[6];
        arrNode[0] = new Node(5,8);
        arrNode[1] = new Node(4,2);
        arrNode[2] = new Node(5,1);
        arrNode[3] = new Node(4,9);
        arrNode[4] = new Node(4,7);
        arrNode[5] = new Node(5,3);
        
        // 정렬조건
        // 1) 첫번째 수가 큰수 우선
        // 2) 두번째 수가 작은 수 우선        
        Arrays.sort(arrNode);
        
        int a=1;

		br.close();
		bw.close();

    }
}

오름차순, 내림차순은 Arrays.sort() 함수를 이용하여 구현이 간단합니다. 하지만 다중차순의 경우 정렬 조건이 1) 첫번째 수가 큰수, 2) 두번째 수가 작은 수 우선이라고 한다면 위 코드와 같이 class 를 만들어 Comparable 을 이용하여 구현하여 줍니다. 정렬 우선순위는 compareTo() 함수를 오버라이드 하여 구현하는데, tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1,  tar 기준으로 우선순위가 동등하면 0,  tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1 이 중요합니다. 

이러한 방법을 통하여 "숫자와 문자를 다음과 같은 우선순위 조건으로 맞추어 정렬 후 출력" 하는 문제도 해결이 가능합니다. (ex, 1)짝수 우선 2)숫자 오름차순 3)문자 오름차순)

정렬은 알고리즘에서 응용을 많이 하는 것으로 방법을 꼭 숙지하여야 합니다.