혼자 놀기의 달인(프로그래머스-연습문제)

문제

코드

import java.util.*;
class Solution {
    static int answer=0;
    public int solution(int[] cards) {
        boolean[] visited=new boolean[cards.length];
        ArrayList<Integer> result=new ArrayList<>();
        dfs(1,visited,result,cards);
        
        return answer;
    }
    static void dfs(int next,boolean[] visited,ArrayList<Integer> result,int[] cards){
        visited[next-1]=true;
        int count=1;
        while(true){
            if(visited[cards[next-1]-1]){
                result.add(count);
                break;
            }
            else{
                visited[cards[next-1]-1]=true;
                next=cards[next-1];
                count++;
            }
        }
        boolean hasNext=false;
        for(int i=0;i<cards.length;i++){
            if(visited[i]) continue;
            else{
                hasNext=true;
                dfs(i+1,visited,result,cards);
                break;
            }
        }
        if(!hasNext){
            Collections.sort(result);
            if(result.size()==1) answer=Math.max(answer,0);
            else answer=Math.max(answer,result.get(result.size()-1)*result.get(result.size()-2));
        }
    }
}

풀이

(1) 방문한 상자를 체크할 visited 배열, 한 번 상자를 선택하여 빈 상자가 나올때까지의 상자 개수를 저장할 result(ArrayList)를 생성하여 dfs()함수에 보내준다.(사실 dfs문제는 아니지만, 내가 처음에 그렇게 풀어서 이름이 dfs로 되어있다.)
(2) dfs에서는 시작할 상자번호를 받고, 그 상자번호를 시작으로 게임을 진행한다. 확인한 상자는 visited 배열에 체크하고, 이미 열었던 상자를 만나면, 이번 턴에서 열었던 상자의 개수를 result에 add해준다.
(3) (2)처럼 한 턴이 끝나면, visited에서 방문하지 않은 상자를 찾아 다시 dfs()함수를 호출하여 준다.
(4) 위 과정을 반복하다가, 방문하지 않은 상자가 없다면, result에서 가장 큰 두 수를 곱해 answer에 넣어준다.

결과

나는 처음에 이 문제를 보고 무조건 dfs로 풀어야겠다고 생각했다. 마침 제한사항에서도 주어진 배열의 크기가 100 이하라는 것을 보고, 그래도 상관없겠다 싶어서 모든 경우의 수를 다 계산하도록 하였다.
막힘없이 코드를 잘 짰는데, 결과는 시간초과가 났다.
그래서 다시 생각했다.
모든 경우의 수를 생각할 필요가 없었다.
8개의 상자가 있다고 쳤을때, 1번 상자를 확인하는 것으로 먼저 시작하든, 2번,3번 상자를 시작으로 확인하든 어차피 결과는 같았다.
모든 경우의 수를 생각하는 것은 매우 비효율적인 일이었다.
그래서 그냥 dfs()함수를 수정하여 1번 상자를 시작으로 한 번만 진행하도록 하였더니, 문제를 해결할 수 있었다.

생각해보면 쉬운 문제였는데, 어렵게 해버렸다. 내가 너무 멍청한 것 처럼 느껴졌다. 좀만 더 생각하자.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges