전력망을 둘로 나누기 복습_2

Об этом предложении

2026.10.04 문제 풀이 나의 코드 소요 시간: 16분 시간 복잡도: $O(n^3)$ import java.util.Set; import java.util.HashSet; class Solution { public int solution(int n, int[][] wires) { int result = 100; Set<Integer> setA = new HashSet<>(); Set<Integer> setB = new HashSet<>(); for (int i = 0; i < wires.length; i++) { setA.add(wires[i][0]); setB.add(wires[i][1]); while(true) { if (setA.size() + setB.size() == wires.length + 1) break; for (int j = 0; j < wires.length; j++) { if (i == j) continue; int w1 = wires[j][0]; int w2 = wires[j][1]; if (setA.contains(w1) || setA.contains(w2)) { setA.add(w1); setA.add(w2); } else if (setB.contains(w1) || setB.contains(w2)) { setB.add(w1); setB.add(w2); } } } result = Math.min(result, Math.abs(setA.size() - setB.size())); setA.clear(); setB.clear(); } return result; } } AI 코드 시간 복잡도: $O(n^3)$ 코드 분석 현재 노드에서 연결된 노드들을 따라간다. 해당 노드와 연결된 다른 노드들을 각각 더하면서 현재 노드가 연결된 총 노드를 재귀적으로 센다. 그 후에 현재 해당 노드를 끊었을 때 n - 2 * sub 로 그 차이가 얼마나 나는지 센다. import java.util.List; import java.util.ArrayList; class Solution { private List<Integer>[] graph; private int n; private int answer = Integer.MAX_VALUE; public int solution(int n, int[][] wires) { this.n = n; graph = new List[n + 1]; for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>(); for (int[] w : wires) { graph[w[0]].add(w[1]); graph[w[1]].add(w[0]); } dfs(1, 0); return answer; } private int dfs(int cur, int parent) { int size = 1; for (int next : graph[cur]) { if (next == parent) continue; int sub = dfs(next, cur); answer = Math.min(answer, Math.abs(n - 2 * sub)); size += sub; } return size; } } 문제 풀이 후기 항상 하는 이야기지만 문제를 푸는 과정에 있어서 반 이상은 설계라는 사실을 다시 한번 깨닫게 되는 계기가 됐다. 끊은 두 전력망 (idx) 선택 두 HashSet에 저장 모든 수가 들어갈 때 까지 while(true) 루프 와 같이 코드를 설계하고 직접 구현하며 문제를 푸는 데 까지 단 16분이 걸렸다. 생각을 깊게 하면서 풀다보니 이전과 달리 코딩 테스트를 하며 머리가 잘 꼬이지 않는다. AI 코드를 보며 이해하기만 하는 데에도 문제를 푸는 것 보다 더 오래 걸렸다. 코드를 이해하고 다시 보면서 "내가 이런 코드를 설계할 수 있는가" 하는 생각이 들었다. 그만큼 재귀함수가 너무 어렵다는 생각이 든다. 지금 내가 할 수 있는건 이런 코드를 반복적으로 쳐가며 이해하는 것 밖에는 없다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.4

Уверенность

49%