프로그래머스 네트워크(computers) 정답 코드

난이도 ★★★★☆

 

문제를 보시려면 여기를 클릭

 

 

 

틀리기 쉬운 입출력 예제

입력	출력
3, {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}} 1, {{1}} 4, {{1,1,1,1}, {1,1,1,0}, {1,1,1,0}, {1,0,0,1}}	3 1 1

 

 

 

힌트

그래프, DFS, BFS로 어렵게 풀지않고, 탐색을 효율적으로 잘하는 방법으로 풀었습니다.   1. computers[i][j] == computers[j][i] 인 점을 이용해 한 방향으로만 서치한다. 2. Set 을 차곡차곡 만들어나가며, 합칠 일이 있으면 효율적으로 잘(?) 합친다.   ※ sets 를 List 가 아닌 Set 으로 바꾸면 34라인의 remove 성능을 올릴 수 있을텐데, 이상하게 실패하는 테스트케이스가 발생하네요. 어떤 케이스에서 실패하는지 ㅜㅜ 못찾겠습니다. 그래서 일단 List 로 통과하긴했는데 도움 부탁드립니다. 해결하였고, 코드를 아래에 추가 첨부하였습니다. 해결한 원리는 내용이 길어 별도 글로 작성하였습니다. (링크. 한마디로 요약하면 hashCode() 때문)

 

 

 

이하는 코드 및 성능입니다.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
 
public class Solution {
    private List<Set<Integer>> sets; // TODO List -> Set
 
    public int solution(int n, int[][] computers) {
        sets = new LinkedList<>();
 
        for (int i = 0; i < n - 1; i++) {
            Set<Integer> iSet = getSet(i);
 
            if (iSet == null) {
                iSet = new HashSet<>();
                iSet.add(i);
                sets.add(iSet);
            }
 
            for (int j = i + 1; j < n; j++) {
                if (computers[i][j] == 1) {
                    Set<Integer> jSet = getSet(j);
 
                    if (iSet == jSet) { // i, j are already in the same set
                        continue;
                    }
 
                    if (jSet == null) {
                        iSet.add(j);
                    } else {
                        // Merge iSet, jSet
                        iSet.addAll(jSet);
                        sets.remove(jSet); // TODO O(n) -> O(1)
                    }
                }
            }
        }
 
        int answer = sets.size();
 
        if (getSet(n - 1) == null) { // 위 서치에서 누락되기 때문에 체크해줌
            answer++;
        }
 
        return answer;
    }
 
    /**
     * @return A set which contains the num, or null
     */
    private Set<Integer> getSet(int num) {
        for (Set<Integer> set : sets) {
            if (set.contains(num)) {
                return set;
            }
        }
 
        return null;
    }
}

 

 

↓↓↓ List 를 Set 으로 바꾼 개선코드 및 성능 ↓↓↓

import java.util.HashSet;
import java.util.Set;
 
public class Solution {
    private Set<Set<Integer>> sets;
 
    public int solution(int n, int[][] computers) {
        sets = new HashSet<>();
 
        for (int i = 0; i < n - 1; i++) {
            Set<Integer> iSet = getSet(i);
 
            if (iSet == null) {
                iSet = new MySet<>();
                iSet.add(i);
                sets.add(iSet);
            }
 
            for (int j = i + 1; j < n; j++) {
                if (computers[i][j] == 1) {
                    Set<Integer> jSet = getSet(j);
 
                    if (iSet == jSet) { // i, j are already in the same set
                        continue;
                    }
 
                    if (jSet == null) {
                        iSet.add(j);
                    } else {
                        // Merge iSet, jSet
                        iSet.addAll(jSet);
                        sets.remove(jSet);
                    }
                }
            }
        }
 
        int answer = sets.size();
 
        if (getSet(n - 1) == null) { // 위 서치에서 누락되기 때문에 체크해줌
            answer++;
        }
 
        return answer;
    }
 
    /**
     * @return A set which contains the num, or null
     */
    private Set<Integer> getSet(int num) {
        for (Set<Integer> set : sets) {
            if (set.contains(num)) {
                return set;
            }
        }
 
        return null;
    }
 
    private class MySet<E> extends HashSet<E> {
 
        @Override
        public int hashCode() {
            return System.identityHashCode(this); // equivalent to Object.hashCode()
        }
    }
}