[Java]Programmers 혼자 놀기의 달인
출처 프로그래머스 혼자 놀기의 달인 접근 숫자 더미를 여러 그룹으로 분리한 뒤, 가장 큰 그룹과 두번째로 큰 그룹을 선택합니다. 완전탐색(DFS) DFS를 통해 숫자 더미를 여러 그룹으로 분리할 수 있습니다. 문제에서 주어진 카드의 최대 개수가 100 이하이므로, 한번씩 방문한다면 O(N)으로 해결이 가능합니다. 100개의 카드가 1개의 그룹인 경우, DFS의 최대 Depth가 100이므로 재귀 호출을 하더라도 StackOverFlow1가 발생하지 않습니다. 재귀 호출을 통해 그룹 분리하기 풀이 import java.util.*; class Solution { // 카드 그룹을 넣을 전역변수 List<Integer> group; public int solution(int[] cards) { group = new ArrayList<>(); // 방문 체크를 위한 변수 boolean[] visited = new boolean[cards.length + 1]; // 카드를 돌면서 그룹화 for (int card : cards) { // 이미 방문한 카드는 다시 방문하지 않음 if (visited[card]) continue; // DFS dfs(card, 0, cards, visited); } // 그룹이 1개면 0 반환 if (group.size() == 1) return 0; // 내림차순 정렬 후 가장 큰 그룹과 두번째로 큰 그룹 곱해서 반환 group.sort(Comparator.reverseOrder()); return group.get(0) * group.get(1); } // DFS void dfs(int now, int cnt, int[] cards, boolean[] visited) { // 이미 방문한 그룹이 다시 등장 -> 같은 사이클(그룹)이므로 그룹에 현재 개수 추가 if (visited[now]) { group.add(cnt); return; } // 방문 체크 visited[now] = true; // now에서 1을 빼줘야 배열 범위를 벗어나지 않음, 방문할 때마다 현재 그룹의 개수 1개씩 추가 dfs(cards[now - 1], cnt + 1, cards, visited); } } 결과 소요시간 7:41 ...