CODEKATA 146 ~ 150

146번 베스트앨범

/*
문제 분석
1. 정보
    - 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개 씩 모아 베스트 앨범을 출시하려 함.
    - 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같음
        - 속한 노래가 많이 재생된 장르를 먼저 수록
        - 장르 내에서 많이 재생된 노래를 먼저 수록
        - 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
2. 목표
    - 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때. 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return
3. 제약 조건
    - genres[i] = 고유번호가 i인 노래의 장르
    - plays[i] = 고유번호가 i인 노래가 재생된 횟수
    - genres와 plays의 길이는 같고, 1 이상 10000 이하
    - 장르 종류는 100개 미만
    - 장르에 속한 곡이 하나라면, 하나의 곡만 선택
    - 모든 장르는 재생된 횟수가 다름

풀이
1. 아이디어
    - HashMap을 활용함
        - hm<장르,장르 정보>를 수록
        - 장르 정보 = 전체 재생 횟수, 많이 재생된 노래 2개 정보가 들어 있음
        - 모든 장르와 plays를 돌면서 hm에 삽입
            - 만약 해당 장르에 대한 hm이 없다면 새로 만들어 삽입
            - 존재한다면 값을 꺼내 비교
                - 많이 재생된 노래가 비어있다면 새로 만들어 삽입
                - 존재한다면 비교하여 업데이트
                - 전체 노래 재생 횟수 추가
        - 모든 장르를 돌고 난 이후
            - 전체 재생 횟수가 많은 순서대로 answer에 값을 담음
            - answer를 return
*/

import java.util.*;

class Solution {

        class Genre{
            int totalPlay;
            int firstIdx;
            int firstPlay;
            int secondIdx;
            int secondPlay;

            public Genre(int totalPlay, int firstIdx, int firstPlay, int secondIdx, int secondPlay) {
                this.totalPlay = totalPlay;
                this.firstIdx = firstIdx;
                this.firstPlay = firstPlay;
                this.secondIdx = secondIdx;
                this.secondPlay = secondPlay;
            }
        }

        public int[] solution(String[] genres, int[] plays) {
            HashMap<String, Genre> hm = new HashMap<>();

            for (int i = 0; i < genres.length; i++) {
                String genre = genres[i];
                int play = plays[i];
                if(!hm.containsKey(genre)){
                    Genre g = new Genre(play, i, play, -1, -1);
                    hm.put(genre, g);
                }else{
                    Genre g = hm.get(genre);
                    g.totalPlay += play;
                    if (play > g.firstPlay) {
                        g.secondPlay = g.firstPlay;
                        g.secondIdx = g.firstIdx;
                        g.firstPlay = play;
                        g.firstIdx = i;
                    }else{
                        if (g.secondPlay == -1 || play > g.secondPlay) {
                            g.secondIdx = i;
                            g.secondPlay = play;
                        }
                    }
                    hm.replace(genre, g);
                }
            }

            List<String> keySet = new ArrayList<>(hm.keySet());
            keySet.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return hm.get(o2).totalPlay - hm.get(o1).totalPlay;
                }
            });

            List<Integer> result = new ArrayList<>();

            for (String s : keySet) {
                Genre genre = hm.get(s);
                result.add(genre.firstIdx);
                if (genre.secondIdx != -1) {
                    result.add(genre.secondIdx);
                }
            }
            int[] answer = new int[result.size()];

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

147번 가장 먼 노드

/*
문제 분석
1. 정보
    - n개의 노드가 있는 그래프가 존재
    - 각 노드는 1부터 n까지 번호가 적혀 있음
    - 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 함.
    - 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미
2. 목표
    - 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return
3. 제약 조건
    - 2 <= 노드의 개수 n <= 20000
    - 간선은 양방향이며 총 1개 이상 50000개 이하의 간선이 존재
    - vertex 배열 각 행 [a,b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미

풀이
1. 아이디어
    - BFS와 dist[] 배열을 사용해 풀이
    - Node class를 생성
        - 도착점, 거리를 가짐
    - dist[] 배열 생성 및 간선이 최대 노드의 개수가 최대 20000개 이므로 30000으로 초기화
    - Queue<Node>를 생성
        - Queue에 시작점인 1번 노드 저장
        - dist[1] = 0으로 초기화
        - 큐가 empty 일때 까지
            - Queue에서 Node 꺼냄
                - 해당 노드와 연결되는 모든 노드들에 대하여
                    - 만약 현재 거리 + 1 보다 이미 저장된 노드가 크다면
                        - 거리 업데이트하고 큐에 저장
                        - 방문 처리하여 다시 방문 못하게 함.
        
*/

import java.util.*;

class Solution {

        class Node {
            int e;
            int d;

            public Node(int e, int d) {
                this.e = e;
                this.d = d;
            }
        }

        List<Integer>[] list;

        public int solution(int n, int[][] edge) {

            list = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) {
                list[i] = new ArrayList<>();
            }

            for (int i = 0; i < edge.length; i++) {
                int s = edge[i][0];
                int e = edge[i][1];
                list[s].add(e);
                list[e].add(s);
            }

            boolean[] visited = new boolean[n + 1];
            int[] dist = new int[n + 1];
            Arrays.fill(dist, 30000);
            Queue<Node> q = new LinkedList<>();
            q.add(new Node(1, 0));
            visited[1] = true;
            dist[1] = 0;
            while (!q.isEmpty()) {
                Node cur = q.poll();
                for (Integer next : list[cur.e]) {
                    if (!visited[next] && dist[next] > cur.d + 1) {
                        dist[next] = cur.d + 1;
                        visited[next] = true;
                        q.add(new Node(next, dist[next]));
                    }
                }
            }

            int answer = 0;
            int max = 0;
            for (int i = 1; i <= n; i++) {
                max = max == 30000 ? max : Math.max(max, dist[i]);
            }

            for (int i : dist) {
                if (i == max) {
                    answer++;
                }
            }

            return answer;
        }
    }

148번 섬 연결하기

/*
문제 분석
1. 정보
    - n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return
    - 다리를 여러번 건너더라도 도달할 수만 있으면 통행 가능
2. 목표
    - n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return
3. 제약 조건
    - 1 <= 섬의 개수 n <= 100
    - costs의 길이 <= ((n - 1) * n ) / 2
    - 임의의 i에 대해 costs[i][0]와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용
    - 같은 연결은 두 번 주어지지 않음. 또한 순서가 바뀌더라도 같은 연결로 봄
    - 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않음.
    - 모든 섬 사이의 다리 건설 비용이 주어지지 않음. 이 경우, 두 섬 사이의 건설이 불가능
    - 연결할 수 없는 섬은 주어지지 않음.
풀이
1. 아이디어
    - 들어온 costs를 costs[i][2] 오름차순으로 정렬함
    - Union-Find를 사용하여 최소 값으로 연결
    - 정렬한 모든 costs를 탐색
        - 아직 연결되지 않았다면 -> find(s) != find(e) 라면
            - union(s,e) 해주고 answer에 d 추가함
            - cnt++ 해주어 cnt가 n-1과 같아지면 종료 할 수 있게끔 구성
*/

import java.util.Arrays;

class Solution {

        int[] parent;

        private int find(int x){
            if(parent[x] == x)return x;
            return parent[x] = find(parent[x]);
        }

        private void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx != ry) {
                parent[ry] = rx;
            }
        }

        public int solution(int n, int[][] costs) {
            Arrays.sort(costs, (o1, o2) -> {
                return o1[2] - o2[2];
            } );
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }

            int answer = 0;
            int cnt = 0;

            for (int[] cost : costs) {
                int s = cost[0];
                int e = cost[1];
                int d = cost[2];
                if (find(s) != find(e)) {
                    union(s, e);
                    answer += d;
                    cnt++;
                    if (cnt == n - 1) {
                        break;
                    }
                }
            }
            return answer;
        }
    }

149번 여행경로

/*
문제 분석
1. 정보
    - 주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다.
    - 항상 "ICN" 공항에서 출발함
2. 목표
    - 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return
3. 제약 조건
    - 모든 공항은 알파벳 대문자 3글자로 이루어짐
    - 주어진 공항 수는 3개 이상 10000개 이하
    - tickets의 각 행 [a,b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미
    - 주어진 항공권은 모두 사용해야 함
    - 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
    - 모든 도시를 방문할 수 없는 경우는 주어지지 않음.

풀이
1. 아이디어
    - 들어온 값을 일단 출발지 오름차순, 도착지 오름차순으로 정렬
    - 티켓의 사용 여부 확인을 위한 boolean[] 배열을 생성
    - DFS 통해 경로를 구함
        - 현재까지 사용한 티켓의 개수와 전체 티켓의 개수가 같으면 path를 answer에 저장하고 return
        - 티켓을 하나씩 확인
            - 만약 현재 위치가 티켓의 시작점이고, 해당 티켓을 사용하지 않았다면,
                - 사용 처리 함
                - path에 해당 티켓 도착지 add
                - dfs를 통해 도착지를 기준으로 다시 구함
                - dfs 끝나면 사용 처리 해제
                - path에서 해당 값 제거
                - 만약 answer가 존재한다면 = 이미 알파벳순 빠른 경로를 구함 -> 더 이상 구하지 않아도 되므로 return
*/

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

class Solution {

        private List<String> answer;
        private boolean[] used;

        public String[] solution(String[][] tickets) {
            Arrays.sort(tickets, (a, b) -> {
                if (a[0].equals(b[0])) return a[1].compareTo(b[1]);
                return a[0].compareTo(b[0]);
            });

            used = new boolean[tickets.length];
            List<String> path = new ArrayList<>();
            path.add("ICN");

            dfs("ICN", tickets, path, 0);

            return answer.toArray(new String[0]);
        }

        private void dfs(String current, String[][] tickets, List<String> path, int cnt) {
            if (cnt == tickets.length) {
                if (answer == null) {
                    answer = new ArrayList<>(path);
                }
                return;
            }

            for (int i = 0; i < tickets.length; i++) {
                if (!used[i] && tickets[i][0].equals(current)) {
                    used[i] = true;
                    path.add(tickets[i][1]);
                    dfs(tickets[i][1], tickets, path, cnt + 1);
                    used[i] = false;
                    path.remove(path.size() - 1);
                    if (answer != null) return;
                }
            }
        }
    }

150번 디스크 컨트롤러

/*
문제 분석
1. 정보
    - 하드디스크는 한 번에 하나의 작업만 수행할 수 있음.
    - 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있음.
    - 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정
    - 우선순위 디스크 컨트롤러는 다음과 같이 동작
        - 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있음. 처음에 이 큐는 비어있음
        - 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선 순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킴.
        - 이때, 작업의 소요 시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높다.
        - 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행함.
        - 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면, 하드 디스크가 작업을 마치자 마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선 순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킴.
2. 목표
    - 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선 순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수 부분을 return
3. 제약 조건
    - 1 <= jobs의 길이 <= 500
    - jobs[i]는 i번 작업에 대한 정보이고 [s,l] 형태임.
        - s는 작업이 요청되는 시점이며 0 <= s <= 1000
        - l은 작업의 소요시간이며 1 <= l <= 1000

풀이
1. 아이디어
    - 우선순위큐를 만들어 작업을 저장함
        - 해당 큐는 작업 소요시간 오름차순, 요청 시각 오름차순, 번호 오름차순 순으로 정렬
    - jobs를 시작 시간 오름차순으로 정렬
    - 끝난 시간을 저장하기위한 배열 finish 생성
    - 처음 jobs를 큐에 넣음
        - 해당 큐에서 값을 poll하여 끝나는 시간을 구함
        - 끝나는 시간을 finish에 저장
        - 끝나는 시간 전까지 시작시간이 포함되는 jobs들을 큐에 넣음
        - 큐 반복
        - 만약 큐가 비어있다면, 다음 번호의 jobs을 삽입함.
*/

import java.util.*;
class Solution {

        class Work implements Comparable<Work> {
            int idx;
            int start;
            int time;

            public Work(int idx, int start, int time) {
                this.idx = idx;
                this.start = start;
                this.time = time;
            }

            @Override
            public int compareTo(Work o) {
                if (this.time == o.time) {
                    if (this.start == o.start) {
                        return this.idx - o.idx;
                    }
                    return this.start - o.start;
                }
                return this.time - o.time;
            }
        }

        public int solution(int[][] jobs) {
            Arrays.sort(jobs, (o1, o2) -> {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            });
            int[] finish = new int[jobs.length];
            PriorityQueue<Work> pq = new PriorityQueue<>();
            pq.add(new Work(0, jobs[0][0], jobs[0][1]));
            int time = jobs[0][0];
            int idx = 1;

            while (!pq.isEmpty()) {
                Work cur = pq.poll();
                time += cur.time;
                finish[cur.idx] = time;

                while (true) {
                    if (idx >= jobs.length) {
                        break;
                    }
                    if (jobs[idx][0] <= time) {
                        pq.add(new Work(idx, jobs[idx][0], jobs[idx][1]));
                        idx++;
                    } else {
                        break;
                    }
                }

                if (idx < jobs.length && pq.isEmpty()) {
                    pq.add(new Work(idx, jobs[idx][0], jobs[idx][1]));
                    time = jobs[idx][0];
                    idx++;
                }
            }
            int answer = 0;
            for (int i = 0; i < finish.length; i++) {
                answer += (finish[i] - jobs[i][0]);
            }
            return answer / finish.length;
        }
    }