2019-03-27

프로그래머스 강좌, 자료구조와 알고리즘 - 3

자료구조와 알고리즘 - 3 link

14강. 큐(Queues)

queues structure
큐는 Stack과 달리 선입선출(FIFO; First-In First-Out) 의 순서로 제어됩니다. 리스트 속에 데이터들의 시작과 끝의 포인터가 존재합니다. 입력(enqueue)시, 리스트의 rear pointer에 추가되며 출력(dequeue)시, 리스트의 front pointer 부분을 꺼내게 됩니다.

실습

목표: 배열과 양방향 연결 리스트 구현시, 연산 복잡도 확인

배열 - 출력시, 모든 개체의 위치를 옮기는 과정에서 O(n) 가 소요
양뱡향 연결 리스트 - 포인터만 변경하게 됨으로 O(1) 소요

15강. 환형 큐(Circular Queue)

circular queues structure
dequeue 과정에서 발생한 front pointer 앞의 공간을 재사용하지 못하는 큐의 단점을 개선하여 리스트의 시작과 끝을 이음으로써 재사용 가능

실습

목표: 환형큐의 enqueue, dequeue, peek 구조를 구현

범위가 제한된 배열을 환형으로 이어서 쓴다는점을 감안하여 배열의 끝과 처음을 연속적으로 사용

16강. 우선순위 큐(Priority Queues)

FIFO 의 특성을 가진 일반적인 큐와 달리 우선순위에 따라 enqueue나 , dequeue의 대상이 선택되는 방식.

실습

목표: 양방향 리스트를 통해 enqueue할 때, 순차검색을 통해 일치하는 위치에 넣는 방식 사용, data의 값이 클수록 높은 우선순위.

enqueue => O(n), dequeue = O(1)
트리구조 사용시 더 유용하나 다음 과정에 진행, 퀵정렬과 비슷한 느낌일것으로 예상

17강. 트리(Trees)

tree data structure
트리의 각 노드를 정해진 순서로 방문하는 것, 순회 (traversal) 연산.

  • 깊이 우선 순회 (DFT; Depth First Traversal)
  • 넓이 우선 순회 (BFT; Breadth First Traversal)

DFT (Depth First Traversal) vs DFS (Depth First Search)? link

  1. DFT는 DFS를 사용합니다.
  2. DFS가 연결된 그래프에 적용되는 알고리즘 인 반면, DFT는 일반적으로 연결이 끊어진 그래프에 적용되는 순회입니다.
  3. DFS는 DFT가 수행하는 동안 각각의 모든 노드를 방문 할 것이라고 보증하지 않았습니다.

하지만 같은것이라 보아도 크게 문제되지 않습니다. 두 용어 모두, 그래프 또는 트리 (모든 트리는 또한 그래프이기도 합니다) 를 대상으로 노드들을 방문하는 순서를 규정하는 방식을 뜻합니다.

근데 tree보단 root모양인데 왜 그렇게 굳어진걸까?

18강. 이진 트리(Binary Trees)

모든 노드의 자식노드; 차수가 2 이하인 트리구조

깊이 우선 순회(DFT; Depth First Traversal)

  • 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
  • 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
  • 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

실습 1

목표: 이진트리의 depth 값 계산하는 기능 구현

class Node:
 # 초기화 & size()
 
    def depth(self):
        # 재귀적으로 호출하며 단말노드 부터 체크
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        # l 과 r 변수에 좌우 노드의 깊이값 저장
        return (l if l > r else r) + 1
        
class BinaryTree:
 # 초기화 & size()
 
    def depth(self):
        # 루트값 유무 확인
        if self.root:
            # root node 부터 depth 확인절차 진행
            return self.root.depth()
        else:
            return 0

실습 2, 3 - 깊이 우선 순회(DFT; Depth First Traversal)

목표: 이진트리의 전위순회, 후위순회 연산 기능 구현

class Node:
 # 초기화 & inorder()
 
 def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal

class BinaryTree:
 # 초기화 & inorder()
 
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

19강 이진 트리 - 넓이 우선 순회(BFT; Breadth First Traversal)

BFT는 트리 구조에서 낮은 level 중 왼쪽 노드부터 순회하게 됩니다. 이로써 DFT와 달리 재귀적으로 구현이 불가합니다. 하지만 Queue를 사용하여 다음에 방문할 노드를 enqueue 해두고 dequeue 하게되면 각각의 level별로 노드를 순회하게 됩니다.

실습

목표: 넓이 우선 순회 기능을 구현

    def bft(self):
        traversal = []
        queue = ArrayQueue()

  # root 존재여부 확인
        if self.root:
            queue.enqueue(self.root)

  # 하위 노드를 queue에 추가하며 노드의 값을 저장
        while not queue.isEmpty():
            node = queue.dequeue()
            traversal.append(node.data)
            if node.left:
                queue.enqueue(node.left)
            if node.right:
                queue.enqueue(node.right)

        return traversal

20강. 이진 탐색 트리(Bianry Search Trees) (1)

binary search tree

시간복잡도

  1. Search Operation - O(n)
  2. Insertion Operation - O(1)
  3. Deletion Operation - O(n)

퀵정렬의 알고리즘을 트리의 형태로 접근하는 방식으로 생각하면 될 것 같다.

실습

목표: BST 에 insert 기능을 구현

    def insert(self, key, data):
     # 키 중복시 예외
        if self.key is key:
            raise KeyError('inserted key is duplicated')

        # key의 비중 확인
        if self.key > key:
            # 하위노드 존재여부 대응
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
                
        return True

21강. 이진 탐색 트리(Binary Search Trees) (2)

트리노드 삭제시 고려사항 참조

  1. 하위노드 X
    zero chilid
  2. 1개의 하위노드
    one chilid
  3. 2개의 하위노드
    two chilid

3번을 처리하며 1, 2의 과정 모두 처리가능

def remove(self, key):
    node, parent = self.lookup(key)

    if node:
        nChildren = node.countChildren()
        
        if nChildren is 0: #하위노드 0개
            if parent:
                if node.key is parent.left.key:
                    parent.left = None
                else:
                    parent.right = None
            else:
                self.root = None
            
        elif nChildren is 1: #하위노드 1개
            childNode = None
            if node.left:
                childNode = node.left
            else:
                childNode = node.right
                
            if parent:
                if node.key is parent.left.key:
                    parent.left = childNode
                else:
                    parent.right = childNode
            else:
                self.root = childNode
                
        else: #하위노드 2개
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
                
            node.key = successor.key
            node.data = successor.data
            
            if successor.key is parent.left.key:
                parent.left = successor.right
            else:
                parent.right = successor.right

        return True

    else:
        return False

22강. 힙(Heaps)

힙 (heap) 도 이진 트리의 한 종류이며 이진 힙 (binary heap) 이라고도 불립니다.

힙에는 최대 힙 (max heap) 과 최소 힙 (min heap) 이 있습니다. 최대 힙과 최소 힙은 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐만 달라지고 완전히 대칭이므로, 여기에서는 최대 힙을 기준으로 설명을 전개하겠습니다. 최대 힙은 세 가지의 성질을 유지하고 있는 이진 트리입니다. 그 세 가지 성질은:

  • 루트 노드가 항상 최댓값을 가진다.
  • 완전 이진 트리이다. (최하위 레벨을 제외하고 모든 레벨이 차있는 상태)
  • 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

완전이진트리의 제약조건으로 인해 log(n)에 비례하는 실행시간을 가짐

배열을 이용해 이진트리 표현시 index 는
*노드 번호 n 기준

  • 상위 : m // 2
  • 좌측 하위: 2 * n
  • 우측 하위: 2 * n + 1

실습

목표: 새로운 노드 추가

    def insert(self, item):
        self.data.append(item)
        index = len(self.data)-1
        
        while index > 1:
            if(self.data[index] > self.data[index // 2]):
             # 아래 방법으로도 손쉽게 값 교환을 할 수 있었다.
             # self.data[index], self.data[index // 2] = self.data[index // 2], self.data[index]
                self.data[index] = self.data[index // 2]
                self.data[index // 2] = item
                index = index // 2
            else:
                break

23강. 힙(Heaps) (2)

최대 힙에서의 삭제. logn의 복잡도

  1. 루트노드의 제거 (루트노드에 최대값이 위치)
  2. 트리의 마지막 노드를 루트노드로 이동
  3. 양쪽 자식노드보다 작을때 까지 서로 값을 교환 (자식노드 중 둘다 클경우 더 큰쪽으로)

최대/최소 힙의 응용

우선 순위 큐 (priority queue)
삽입(enqueue)시, 느슨한 정렬(=반정렬; 큰값이 상위, 작은값이 하위에 있음)을 이루고 있도록 함. O(logn) 의 복잡도
출력(dequeue)시, 최대값을 순서대로 추출. O(logn) 의 복잡도

힙 정렬 (heap sort)
정렬되지 않은 원소를 최대힙에 삽입, O(logn) X 힙이 빌때까지 삭제순으로 정렬, O(logn) = O(nlogn)

2019-03-26

개발 환경의 자동화, CI

Continuous Integration

CI(Continuous Integration), 지속적 통합이란 소스관리, 빌드, 배포 등의 구조를 자동화 함으로써 소프트웨어 개발에 위험을 줄이는 방법으로 사용되고 있습니다.
Imgur

CI 구성의 핵심 4요소

CI Server

빌드 스크립트를 작성하고 자동화 프로세스를 구성하여 빌드. 테스트를 포함한 자동화 절차를 통해 검증하며 오류를 감지한다.
예) Jenkins, Travis

Source Control, Version Control

소스 코드 관리 및 팀 단위 구성의 프로젝트 진행시 필수적이며 오류 수정과정을 돕는다.
예) Subversion(SVN), Git, GitLab

Build Tool

Source Control에서 구성된 소스 코드를 실행 가능한 형태로 가공하며 사전에 구성된 테스트 절차를 진행하여 구성된 소스 코드의 결함을 파악한다.
예) Maven, Gradle, Ant

Test Tool

사전 구성된 테스트 코드에 따라서 일련의 검증과정을 거친다. 기능의 검증 뿐만 아니라 코드 품질에 대해서도 검증과정이 진행되는것이 좋다.
예) Junit, SonarQube

참조

프로그래머스 알고리즘, 가장 큰 수

목표 (문제)

주어진 배열의 수를 조합하여 가장 큰 수를 만든다.

조건

  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

잡설

생각한 과정에서 문제가 생겨 더이상 진행하지 못하고 다른 풀이를 보았는데 comparator를 사용한걸 알게되었다. 해당 comparator에 대해 기록해봐야겠다.

코드

 public static String solution(int[] numbers) {

    String answer ="";
    List<String> list = new ArrayList<>();
    int length = numbers.length;

    for(int i=0; i<length; i++){
        list.add(Integer.toString(numbers[i]));
    }

    int size = list.size();
    Collections.sort(list, new Comparator<String>(){
        @Override
        public int compare(String num1,String num2){
            return (num2+num1).compareTo(num1+num2);
        }
    });
    if(list.get(0).equals("0")){
        return "0";
    }

    for(int i=0; i<size; i++){
        answer = answer + list.get(i);
    }
    return answer;
}

참조

잘못된 시도

잡설

처음 구조를 작성할때 Collections.sort를 string 일때 정렬하면 자리값 별로 비교하던것에 꽂혀서 구성을 했던것이 문제였던 것 같다. 비교하는 과정이 올바르지 않았기에 발생한 문제인것으로 생각한다.

코드

public static String solution(int[] numbers) {
 // int[0~9][0~n] 2차배열 생성
 List<LinkedList<String>> numberGroup = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     numberGroup.add(new LinkedList<>());
 }

 // 맨앞자리 숫자값으로 분류하여 배열 삽입
 for (int num : numbers) {
     String temp = Integer.toString(num);
     int numIndex = Integer.parseInt(temp.substring(0, 1));// 앞부분 때기
     numberGroup.get(numIndex).add(temp);
 }

 // 배열 정렬
 for (LinkedList<String> numberList : numberGroup) {
        Collections.sort(numberList, Collections.reverseOrder());
 }

 // 문자열 병합
 StringBuilder result = new StringBuilder();
 for (int i = numberGroup.size() - 1; i >= 0; i--) {
     System.out.println(numberGroup.get(i));
     for (String number : numberGroup.get(i)) {
         result.append(number);
     }
 }
 return result.toString();
}
참조 - https://n1tjrgns.tistory.com/139

프로그래머스 알고리즘, 모의고사

목표 (문제)

1~5까지를 일정한 패턴으로 반복할때, 그 값들을 주어진 answers와 비교하여 일치하는 값의 갯수들을 배열로 반환하시요.

조건

  • answers 의 길이는 최대 10,000 입니다.
  • 배열값은 반드시 1, 2, 3, 4, 5 중 하나입니다.
  • 일치하는 개수가 동일할 경우, Index를 기준으로 오름차순 정렬해주세요.
  • 일치하는 값이 모두 없을때, 두 반환합니다.

코드

public class Main {

    public static void main(String[] args) {
//        int[] answers = { 1, 2, 3, 4, 5 };
//        int[] answers = { 1,3,2,4,2 };
        int[] answers = { 3, 1, 1 };
//        int[] answers = { 4, 4 };

        for (int val : solution(numbers)) {
            System.out.print(val + ",");
        }
    }

    public static int[] solution(int[] answers) {
        int persons[][] = { { 1, 2, 3, 4, 5 }, { 2, 1, 2, 3, 2, 4, 2, 5 }, { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 } };
        int result[][] = new int[persons.length][2];

  // 결과값 구조 초기화
        for (int i = 0, len = result.length; i < len; i++) {
            result[i][0] = i + 1;
            result[i][1] = 0;
        }
  
  // 패턴대로 순환하며 일치 개수 체크
        for (int i = 0, len = answers.length; i < len; i++) {
            for (int j = 0; j < persons.length; j++) {
                if (persons[j][i % persons[j].length] == answers[i])
                    result[j][1]++;
            }
        }

  // 일치개수 기반하여 정렬
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] back, int[] front) {
                return front[1] - back[1];
            }
        });

  // 출력할 길이 지정하여 반환값 설정
        int length = result[0][1] == 0 ? result.length : 1;
        int[] answer = new int[length];
        for (int i = 0; i < length; i++) {
            answer[i] = result[i][0];
        }

        return answer;
    }
}

프로그래머스 알고리즘, 소수찾기2

목표 (문제)

주어진 numbers의 각각 숫자들을 조합하여 만들 수 있는 모든 소수의 수를 반환하세요.

조건

  • numbers는 길이가 1 ~ 7 인 문자열입니다.
  • numbers는 0~9 까지 숫자값만으로 이루어져 있습니다.
  • 013은 0, 1, 3 숫자로 조합하면 됩니다.
  • 11과 011은 같은 숫자로 취급합니다.

코드

동작

오류 발생

Set<Integer> lhs = new LinkedHashSet<Integer>();

public int solution(String numbers) {
    makeCombination("", numbers);
    return getPrimeCount(new LinkedList<Integer>(lhs));
}

public int getPrimeCount(LinkedList<Integer> numbers) {
    for (int prime : new int[] { 2, 3, 5, 7 }) {
        for (int i = 0; i < numbers.size(); i++) {
            int number = numbers.get(i);
            if (number < 2 || (number % prime == 0 && number != prime)) {
                numbers.remove(i--);
            }
        }
    }
    return numbers.size();
}

public void makeCombination(String s, String number) {
    if (number.length() == 0) {
        if (!s.equals("")) {
            lhs.add(Integer.parseInt(s));
        }
    } else {
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s + number.charAt(i), number.substring(0, i) + number.substring(i + 1, number.length()));
        }
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s, number.substring(0, i) + number.substring(i + 1, number.length()));
        }
    }
}

잡설

소수 구하는건 생각해냈지만 숫자조합을 도저히 생각해낼 수 없었기에 결국 찾아보게 되었다. 이곳 에서

프로그래머스 알고리즘, H-index

목표 (문제)

int 배열값 들을 H라고 하고 전체 배열에서 조건에 해당되는 배열값의 갯수가 n이라고 할때, n값의 최대를 구하시요.

조건

  • H는 n 이상
  • n의 값은 1 ~ 1,000
  • H의 값은 0 ~ 10,000

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
//        int[] numbers = { 3, 0, 6, 1, 5 };
//        int[] numbers = { 0, 0, 0 };
        int[] numbers = { 22, 42 };

        System.out.println(solution(numbers));
    }

    public static int[] solution(int[] citations) {
        int answer = 0;

        //정렬위해 List 변환
        List<Integer> list = Arrays.stream(citations).boxed().collect(Collectors.toList());
        //정렬
        Collections.sort(list, Collections.reverseOrder());
        
        //X의 값이 H를 넘지않는 범위에서 순회
        for(Integer citation : list) {
            if (answer < citation) {
                answer++;
            } else {
                break;
            }
        }
        
        return answer;
    }
}

잡설

 boxed() 메서드는 int, long, double 요소를 Integer, Long, Double 요소로 변환하여 저장

프로그래머스 알고리즘, K번째 수

목표 (문제)

2차배열인 commands 의 값마다 [i][0]과 [i][1]번을 시작과 끝으로 array 배열에서 분리 후,
오름차순 정렬 하여 command[i][2]의 index에 해당하는 값들을 return 한다.

조건

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

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        int[] array = { 1, 5, 2, 6, 3, 7, 4 };
        int[][] commands = { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 } };

        for (int val : solution(a, b)) {
            System.out.print(val + ",");
        }
    }

    public static int[] solution(int[] array, int[][] commands) {
        List<Integer> answer = new ArrayList<>();

        for (int cmdIndex = 0; cmdIndex < commands.length; cmdIndex++) {
            int from = --commands[cmdIndex][0];
            int to = commands[cmdIndex][1];

            int[] splitArray = Arrays.copyOfRange(array, from, to);
            Arrays.sort(splitArray);

            int selectedIndex = commands[cmdIndex][2] - 1;
            answer.add(splitArray[selectedIndex]);
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}

Bucket Sort

버킷 정렬(bucket sort)

인터넷 자료를 보던중 컴퓨터의 세계 밖에서 발견한 O(n) 소팅 이란 게시글을 보게되었다.
보통 정렬 알고리즘은 O(nlogn) 정도가 제일 빠른것으로 표를 통해 보았는데
댓글중 버킷 정렬에 대한 댓글로 버킷정렬에 대해 얘기가 나와 궁금해졌다.

절차

progress

코드

public void bucketSort(int[] numbers) {
 // int[0~9][0~n] 2차배열 생성
 List<LinkedList<String>> numberGroup = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     numberGroup.add(new LinkedList<>());
 }

 // 맨앞자리 숫자값으로 분류하여 배열 삽입
 for (int num : numbers) {
     String temp = Integer.toString(num);
     int numIndex = Integer.parseInt(temp.substring(0, 1));
     numberGroup.get(numIndex).add(temp);
 }

 // 배열 정렬
 for (LinkedList<String> numberList : numberGroup) {
        Collections.sort(numberList, Collections.reverseOrder());
 }

잡설

처음에 버킷정렬만 들었을 땐 감이 안왔는데 구조를 보자마자 생각난게
알고리즘 풀이 시도중 K번째 수에 사용한 코드가 떠올랐다.
버킷정렬을 고려하고 짠건 아닌데 이런 형태의 정렬구조가 있었음을 알았다.
코드는 해당 풀이에서 가져왔는데 아마 더 나은 예시코드 가 있지않을까?
사실 알게 모르게 다양한 정렬을 쓰고있을 것 이다.

프로그래머스 알고리즘, 완주하지 못한 선수

목표 (문제)

completion 배열에서 participant 배열 중 제외된 대상 값을 return

조건

  • participant 배열 속 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 선수명이 같은 경우가 있을 수 있습니다.

코드

public String solution(String[] participant, String[] completion) {
    HashMap<String, Integer> start = new HashMap<String, Integer>();
    for (String item : participant) {
        Integer hashItem = start.get(item);
        if (hashItem == null) {
            start.put(item, 1);
        } else {
            start.put(item, hashItem + 1);
        }
    }

    HashMap<String, Integer> retire = (HashMap) start.clone();
    for (String item : completion) {
        retire.put(item, retire.get(item) - 1);
    }
    
    for(String item : retire.keySet()) {
        if(retire.get(item)> 0) {
            return item;
        }
    }
    return null;
}

프로그래머스 알고리즘, 베스트 앨범

목표 (문제)

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

조건

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

잡설

domain 구성하면 복잡하지 않게 해결될거같긴 한데 다른방법도 해보고 싶어서
나름 구성해보았으나… 저 sort 메서드를 합칠 방법이 뭐가 있을까?
분명히 저렇게 중복되는걸 자료형 선택해서 하나의 메서드로 합쳐 처리하는 방법이 있을텐데
그걸 모르겠네

코드

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

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, HashMap<Integer, Integer>> music = new HashMap<>();
        HashMap<String, Integer> total = new HashMap<>();

        for (int index = 0, maxIndex = plays.length; index < maxIndex; index++) {
            HashMap<Integer, Integer> item;
            if (music.containsKey(genres[index])) {
                item = music.get(genres[index]);
                total.put(genres[index], total.get(genres[index]) + plays[index]);
            } else {
                item = new HashMap<>();
                total.put(genres[index], plays[index]);
            }
            item.put(index, plays[index]);
            music.put(genres[index], item);
        }

        List<Integer> answer = new ArrayList<>();
        for (String item : sortTotal(total).keySet()) {
            Set<Integer> sortedMusic = sortMusic(music.get(item)).keySet();
            int index = 0;
            for (Integer item2 : sortedMusic) {
                if (index++ > 1 ) {
                    break;
                }
                answer.add(item2);
            }
        }
        return answer.stream().mapToInt(i->i).toArray();
    }

    public LinkedHashMap<String, Integer> sortTotal(HashMap<String, Integer> total) {
        List<Entry<String, Integer>> list = new ArrayList<>(total.entrySet());
        list.sort(Entry.comparingByValue(Comparator.reverseOrder()));

        LinkedHashMap<String, Integer> sortedTotal = new LinkedHashMap<>();
        for (Entry<String, Integer> entry : list) {
            sortedTotal.put(entry.getKey(), entry.getValue());
        }

        return sortedTotal;
    }

    public LinkedHashMap<Integer, Integer> sortMusic(HashMap<Integer, Integer> music) {
        List<Entry<Integer, Integer>> list = new ArrayList<>(music.entrySet());
        list.sort(Entry.comparingByValue(Comparator.reverseOrder()));

        LinkedHashMap<Integer, Integer> sortedMusic = new LinkedHashMap<>();
        for (Entry<Integer, Integer> entry : list) {
            sortedMusic.put(entry.getKey(), entry.getValue());
        }

        return sortedMusic;
    }
}