[프로그래머스] 혼자 놀기의 달인 자바

 

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=java 

프로그래머스

 

접근 방법

처음에 cards안에 card를 기준으로 방문체크를 하면서 dfs를 순회했는데 테케5번에서 에러가 낫다.

코드를 자세히 보니 dfs로 들어갈 때 현재 내 배열이 아니라 다음 배열에 true표시를 하는 것 같았고 card로 순회하지 않고 배열 인덱스를 기준으로 순회하니 해결됐다.

 

틀렸던 코드

package programmers.level2;

import java.util.ArrayList;
import java.util.Collections;

public class 혼자놀기의달인 {
    static boolean[] visited;
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        int[] cards = {2,1,4,3,7,5,6};
        System.out.println(solution(cards));
    }

    public static int solution(int[] cards) {
        visited = new boolean[101];
        for (int i = 0; i < cards.length; i++) {
            if(visited[cards[i]]) continue;
            dfs(cards, cards[i]-1, 0);
        }
        if (list.size() == 1) return 0;
        Collections.sort(list, Collections.reverseOrder());
        return list.get(0) * list.get(1);
    }

    private static void dfs(int[] cards, int card, int count) {
        if (visited[card]) {
            list.add(count);
            return;
        }
        visited[card] = true;
        dfs(cards, cards[card]-1, count+1);
    }
}

 

정답 코드

package programmers.level2;

import java.util.ArrayList;
import java.util.Collections;

public class 혼자놀기의달인 {
    static boolean[] visited;
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        int[] cards = {2,1,4,3,7,5,6};
        System.out.println(solution(cards));
    }

    public static int solution(int[] cards) {
        visited = new boolean[cards.length];
        for (int i = 0; i < cards.length; i++) {
            if(visited[i]) continue;
            dfs(cards, i, 0);
        }
        if (list.size() == 1) return 0;
        Collections.sort(list, Collections.reverseOrder());
        return list.get(0) * list.get(1);
    }

    private static void dfs(int[] cards, int index, int count) {
        if (visited[index]) {
            list.add(count);
            return;
        }
        visited[index] = true;
        dfs(cards, cards[index]-1, count+1);
    }
}

 

 

**추가

첫 코드가 틀린 이유는

        for (int i = 0; i < cards.length; i++) {
            if(visited[cards[i]]) continue;
            dfs(cards, cards[i]-1, 0);
        }

여기서 방문체크를 할 때 cards[i]에 -1을 빼주지 않아서 발생한 에러였다