백준 9466번 텀 프로젝트 [ Java ]

9466번: 텀 프로젝트

계속 틀리는 원인을 찾지 못해 다른분의 코드를 참고했습니다.

틀린코드 ( 메모리 초과 ) 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int i=0; i<T; i++){
            int N = Integer.parseInt(br.readLine());
            int[] students = new int[N+1];
            int[] isTeam = new int[N+1]; // -2 팀은 되지만 혼자 -1 팀 안됨 0 확인안함 1 팀 됨
            int result = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=1; j<=N; j++)
                students[j] = Integer.parseInt(st.nextToken());
            for (int j=1; j<=N; j++){
                // 선택한 학생이 본인일 때
                if (students[j]==j){
                    isTeam[j] = -2;
                    continue;
                }
                // 이미 팀이 확정 되었을 때
                if (isTeam[j]==1) continue;
                // 선택한 학생이 결정이 났을 때
                if (isTeam[students[j]] != 0) {
                    isTeam[j] = isTeam[students[j]];
                    // -2, -1의 경우
                    if (isTeam[j] < 0) result++;
                    continue;
                }
                Stack<Integer> stack = new Stack<>();
                stack.push(j);
                while (true){
                    if (stack.peek() == students[stack.peek()] || isTeam[stack.peek()]<0){
                        while(!stack.empty())
                            isTeam[stack.pop()] = -1;
                        result++;
                        break;
                    }
                    if (students[stack.peek()] == j || isTeam[stack.peek()]==1){
                        while(!stack.empty())
                            isTeam[stack.pop()] = 1;
                        break;
                    }
                    stack.push(students[stack.peek()]);
                }
            }
            sb.append(result+"\n");
        }
        System.out.print(sb);
    }
}

참고한 코드

import java.util.*;

public class Main {
    static int[] students; // 학생 배열
    static int[] check; // 몇 번째로 방문하는 것인지
    static int[] startV; // 시작 정점
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- >0){
            int N = sc.nextInt();
            students = new int[N+1];
            check = new int[N+1];
            startV = new int[N+1];

            for (int i=1; i<=N; i++)
                students[i] = sc.nextInt();
            int result = 0;
            for (int i=1; i<=N; i++){
                if (check[i]==0) // 방문하지 않았다면
                    result += dfs(i, 1, i);
            }
            System.out.println(N-result);
        }
    }
    static int dfs(int i, int cnt, int start){
        if (check[i] != 0){ // 이미 방문했던 정점이면
            if (start != startV[i]) // 시작 정점과 다른지 확인
                return 0;
            return cnt-check[i]; // 같으면 몇 번째 방문한 정점인지
        }
        check[i] = cnt; // 몇 번째 방문한건지 저장
        startV[i] = start;
        return dfs(students[i], cnt+1, start);
    }
}

 

https://dundung.tistory.com/32

백준 9466 텀 프로젝트 Java