프로그래머스 전력망을 둘로 나누기, 베스트앨범, 의상

✂️프로그래머스 : 전력망을 둘로 나누기 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

✂️ 인접행렬로 그래프를 바꿔서 푸는 문제를 최근에 안 풀었어서 이번기회에 다시 풀어봤다. 역시 안 풀면 계속 머리가 굳는 것 같다.. 

✂️ 인접행렬로 그래프를 바꾸려면 아래 조건을 확인해봐야 한다. 

• 노드 개수에 비해 에지가 적으면 효율성이 떨어지므로 비교해보기 
• 노드 개수가 너무 많으면 메모리 초과날 수도 있음. 

✂️ 이 문제에서는 에지 개수가 N-1이므로 첫 번째 조건을 충족

✂️ 노드 개수 또한 100개 이하이므로 두 번째 조건도 충족

✂️ 완전 탐색 문제인 만큼 그냥 선 하나 자르고 쭉 DFS 돌리는 방식으로 풀었다. 

 

✂️ 코드 

class Solution {
    int[][] graph;
    boolean[] visited;
    public int solution(int n, int[][] wires) {
        graph = new int[n+1][n+1];
        visited = new boolean[n+1];
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < wires.length; i++) {
            graph[wires[i][0]][wires[i][1]] = 1;
            graph[wires[i][1]][wires[i][0]] = 1;
        }
        
        for (int i = 0; i < wires.length; i++) {
            graph[wires[i][0]][wires[i][1]] = 0;
            graph[wires[i][1]][wires[i][0]] = 0;
            
            DFS(wires[i][0]);
            
            int temp = 0;
            for (int j = 1; j <= n; j++) {
                if (visited[j]) {
                    temp++;
                }
            }
            answer = Math.min (answer, Math.abs(n - temp * 2));
            
            visited = new boolean[n+1];
            graph[wires[i][0]][wires[i][1]] = 1;
            graph[wires[i][1]][wires[i][0]] = 1;
        }
        return answer;
    }
    
    public void DFS(int start) {
        if (visited[start]) {
            return;
        } 
        visited[start] = true;
        for (int i = 1; i < graph[start].length; i++) {
            if (graph[start][i] == 1) {
                DFS(i);
            }
        }
    }
}

 

---

 

 

🎵프로그래머스 : 베스트앨범

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

프로그래머스

 

🎵어차피 각 장르 당 곡은 2개씩밖에 못 실어서, 그냥 용도별로 해시맵을 나눠서 다소 무식하게 ? 풀었다. 

🎵 count 맵은 각 장르별 총 재생횟수 계산을 위한 해시맵, 재생횟수(value)기준으로 역순정렬해서 앨범에 실으면 된다. 

 

🎵 맵 value기준으로 정렬하는거 코드 어떻게 외워서 침?? 진짜 복잡해서 머리에 잘 안들어온다;; 

🎵 first, second는 각 장르별 제일 많이 재생된 애들, 2번째로 많이 재생된 애들 담는 용도이다. 얘네 갱신하느라 코드가 복잡해졌다.

 

🎵 참고로, 처음에 테스트 케이스 2,15만 틀리길래 왜그런가 했는데 장르 내 동일 재생횟수면 번호 작은게 우선순위다.

🎵 어차피 순서대로 읽으므로, 동일 값이 나오면 나중에 읽은 음악보다 먼저 읽은 음악이 고유번호가 낮아서 우선순위를 갖는다. 

 

🎵 전체 코드 

import java.util.*;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> count = new HashMap<>();
        Map<String, Music> first = new HashMap<>();
        Map<String, Music> second = new HashMap<>();
        List<Integer> answer = new ArrayList<>();
        
        for (int i = 0; i < plays.length; i++) {
            if (count.containsKey(genres[i])) {
                count.put(genres[i], count.get(genres[i]) + plays[i]);
            } else {
                count.put(genres[i], plays[i]);
            }
            
            int tempFirst = -1;
            int tempSecond = -1;
            
            if (first.containsKey(genres[i])) {
                tempFirst = first.get(genres[i]).plays;
            }
            if (second.containsKey(genres[i])) {
                tempSecond = second.get(genres[i]).plays;
            }
            
            if (tempFirst == -1 && tempSecond == -1) { // 둘다 비어있는 경우 
                first.put(genres[i], new Music(i, plays[i]));
            } 
            else if (tempFirst != -1 && tempSecond == -1) { // 두 번째만 비어있는 경우 
                if (tempFirst > plays[i]) { // 첫 번째거가 더 크면 2번째에 그냥 넣기. 
                    second.put(genres[i], new Music(i, plays[i]));
                } 
                else { // 첫 번째꺼를 second로 민다. 
                    second.put(genres[i], first.get(genres[i]));
                    first.put(genres[i], new Music(i, plays[i]));
                }
            } 
            else { // 둘다 값이 있어서 비교 필요
                if (tempFirst >= plays[i]) {
                    if (tempSecond < plays[i]) { // 같을 경우엔 어차피 나중에 읽은게 뒤 순위를 가지므로..
                        second.put(genres[i] , new Music(i, plays[i]));
                    }
                }
                else {
                    second.put(genres[i], first.get(genres[i]));
                    first.put(genres[i], new Music(i, plays[i]));
                }
            }
        }
        
        
        List<Map.Entry<String, Integer>> entries = new LinkedList<>(count.entrySet());
        entries.sort(Map.Entry.comparingByValue(Collections.reverseOrder()));
        
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            if (second.containsKey(key)) {
                answer.add(first.get(key).id);
                answer.add(second.get(key).id);
            } else {
                answer.add(first.get(key).id);
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
    
    
    class Music {
        int id;
        int plays;
        
        public Music (int id, int plays) {
            this.id = id;
            this.plays = plays;
        }
    }
}

 

 

---

🎀 프로그래머스 : 의상

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

🎀 종류 + 해당하는 의상 개수를 HashMap에 저장한다. 

🎀 조합을 구할 때 모자를 빼놓고 한다던가, 안경을 안 쓴다던가 하는 식으로 모든 종류의 옷을 입을 필요는 없다. 

🎀 따라서, 안 입는 경우를 더해서 조합을 구한 후, 아무것도 걸치지 않은 상태 1을 빼주면 정답이 된다. 

🎀 전체 코드

 

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> closet = new HashMap<>();
        for (int i = 0; i < clothes.length; i++) {
            if (closet.containsKey(clothes[i][1])) {
                closet.put(clothes[i][1], closet.get(clothes[i][1]) + 1);
            } else {
                 closet.put(clothes[i][1], 1);
            }
        }
        List<Integer> count = new ArrayList<>(closet.values());
        for (int i = 0; i < count.size(); i++) {
            answer *= (count.get(i) + 1);
        }
        
        return (answer - 1);
    }    
}