[프로그래머스/Level2] 혼자 놀기의 달인 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS

필요 자료구조
- 그룹 별 상자 갯수 저장할 int형 우선순위 큐 (상자 갯수가 많은 순으로 내림차순 정렬)
- 상자가 열림/닫힘을 표현할 boolean형 방문 표시 배열

 

 

1. cards 배열의 0부터 cards.length-1번째 원소까지 돌며 방문하지 않은 칸이 있다면, 방문 처리하고 그룹 내에 포함된 상자 수를 세러 간다. (dfs 메소드)

2. DFS 메소드 구현

   - 종료 조건 : 열었던 상자인 경우(visited[idx] == true), 여태껏 구한 상자 갯수를 큐에 저장하고 리턴한다.

   - 만약 방문하지 않았다면, 방문 처리하고, 배열의 해당 idx-1 위치로 이동하면서 (현재 그룹 내 상자 수+1)한 값을 함께 가져간다.

private static void dfs(int idx, int depth) {
    if(visited[idx]) {  // 열었던 상자인 경우
        pq.add(depth);  // 상자 갯수를 큐에 저장하고 리턴
        return;
    }

    visited[idx] = true;
    dfs(cards[idx] - 1, depth + 1); // 배열의 해당 idx-1 위치로 이동하면서 그룹 내 상자 수+1
}

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] cards;
    static PriorityQueue<Integer> pq;   // 상자 그룹 수 저장용 우선순위 큐
    static boolean[] visited;
    static int answer = 0;  // 얻을 수 있는 최고 점수
    
    public int solution(int[] cards) {
        this.cards = cards;
        
        pq = new PriorityQueue<>(Collections.reverseOrder());    // 리스트 크기 기준 정렬
        visited = new boolean[cards.length];
        
        for(int i = 0 ; i < cards.length ; i++) {
            if(!visited[i])
                dfs(i, 0);
        }
        
        if(pq.size() != 1)  // 그룹이 2개 이상인 경우, 1번 그룹 수 * 2번 그룹 수
            answer = pq.poll() * pq.poll();
        
        return answer;
    }
    
    private static void dfs(int idx, int depth) {
        if(visited[idx]) {  // 열었던 상자인 경우
            pq.add(depth);  // 연 상자 갯수를 큐에 저장하고 리턴
            return;
        }
        
        visited[idx] = true;
        dfs(cards[idx] - 1, depth + 1); // 다음 위치로 이동하면서 그룹 내 상자 수+1
    }
}

 

 

 

 

➕ 다른 풀이 방식

나의 추구미.. 이렇게 풀려고 했었다!!!

import java.util.*;

class Solution {
    public int solution(int[] cards) {
        int n = cards.length;
        boolean[] visited = new boolean[n];
        List<Integer> groups = new ArrayList<>();	// 각 그룹별 상자 갯수 저장

        for (int i = 0; i < n; i++) {
            int now = i;
            int cnt = 0;	// 연 상자 갯수
            
            while (!visited[now]) {
                cnt++;
                visited[now] = true;
                now = cards[now] - 1;
            }
            groups.add(cnt);
        }
        
        Collections.sort(groups, Comparator.reverseOrder());	// 상자 갯수 많은 순 내림차순 정렬
        return (groups.size() == 1) ? 0 : groups.get(0) * groups.get(1);
    }
}

 

 

+ 유니온파인드도 사용한 방식

프로그래머스

---

💦 어려웠던 점

- 각 그룹 별 원소를 모두 저장하고 그 길이를 구하려고 했었다. (List<List<Integer>>) ⇒ 그냥 int형 변수를 활용해 그룹별 갯수만 저장하면 되었다. (List<Integer>)

 

 

🧐 새로 알게 된 내용

- 꼭 그릅의 모든 원소를 다 저장할 생각하지 말고, 그냥 변수 하나만 사용해 해당 그룹의 갯수를 저장하도록 하자,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

(Java) 프로그래머스 - 혼자 놀기의 달인