글 읽기 - 시간초과 관련해서 질문있습니다 ㅠ

anhyunsoo 6년 전 0

1.계속 시간초과가 뜨는데 Arraylist에서 Contain 이나 Indexof 같은 메소드가 시간을 많이뺏어먹나요?

2.ArrayList 보다 Queue를 활용하는게 시간단축에 확실한 효과가 있나요??

import java.util.ArrayList;
import java.util.Scanner;

public class Main2 {
	static int[] a, A;
	static ArrayList<Integer> P;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Test = sc.nextInt();
		for (int tc = 0; tc < Test; tc++) {
			int n = sc.nextInt();

			a = new int[n + 1];  //입력받을 배열
			A = new int[n + 1];  //A[i] = 1일시 팀확정 0은 아직 안정함  -1 은 못짬 
			int result = 0;
			for (int i = 0; i < n; i++) {
				a[i + 1] = sc.nextInt();
			}
			for (int i = 1; i < n + 1; i++) {//자기혼자 팀하려는 인원 먼저 색출
				if (a[i] == i) {
					A[i] = 1;
				}
			}

			P = new ArrayList<Integer>();
			for (int i = 1; i < n + 1; i++) {
				if (A[i] != 0) //다른과정에서 이미 확정된 경우 Continue
					continue;
				

				P.add(i);
				int x = a[i];  //포인터로 사용
				if (A[x] == 1) {
					A[i] = -1;
					continue;
				}
				dfs(x);
				P.clear();
			}
			for (int j = 0; j < n; j++) {
				if (A[j + 1] == -1) {

					result++;
			
				}
			}
			System.out.println(result);
		}
	}

	private static void dfs(int x) {
		P.add(x);
		if (A[a[x]] != 0) {   //다음 가르키는 값이 이미 팀짰거나 탈락으로 확정된 인원이 나오는경우 queue에 모든값 
			                    //탈락행
			for (int j = 0; j < P.size(); j++) {
		
				A[P.get(j)] = -1;
			}
		} else if (P.contains(a[x])) {
			                                                  
			for (int j = P.indexOf(a[x]); j < P.size(); j++) {
			 //싸이클 발견시 싸이클 시작지점부터 끝까지 팀확정
				A[P.get(j)] = 1;
			}
			for (int j = 0; j < P.indexOf(a[x]); j++) { //싸이클 앞에 닫힌 인원들 탈락확정
		
				A[P.get(j)] = -1;
			}
		} else {

			    //dfs반복
			x = a[x];

			dfs(x);
		}

	}
}

zlzmsrhak 6년 전 0

ArrayList의 contain, indexof의 메소드는 모든 원소를 순회하기 때문에 선형시간만큼 소요됩니다.

즉, 위의 코드는 O(N^2) 정도의 시간복잡도를 가지게 되겠습니다.

자바는 잘 모르지만, Hashmap과 같은 container를 검색해 보시는 것이 도움이 될 것 같습니다.

anhyunsoo 6년 전 0

Hashmap을 이용해봤는데 1퍼센트에서 또 막히네요..시간초과만 계속 뜹니다. ㅜㅜㅜㅜ

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    static Queue<Integer> P;
    static HashMap<Integer, Integer> hm;
    static int[] g;
    static int result_n;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TEST = sc.nextInt();
        for (int tc = 0; tc < TEST; tc++) {
            int n = sc.nextInt();
            g = new int[n + 1];
            int result = 0;
            hm = new HashMap<>();
            P = new LinkedList<Integer>();
            for (int i = 1; i < n + 1; i++) {
                int temp = sc.nextInt();
                hm.put(i, temp);
                if (i == temp) {
                    g[i] = 1;               //g[] 에서 1은 루프확정 0 은 미확 -1은 팀탈락
                    result_n++;
                }
            }
            int gg = 0;
            for (int i = 1; i < n + 1; i++) {
 
                if (result_n == n)//result_n은 확정 된 노드의 갯수입니다 앞선루프에서 모든 vertex확정된다면 반복문종료
                    break;
                if (g[i] != 0)
                    continue;
                if (g[hm.get(i)] != 0 && g[i] == 0) {       //이미 루프가 정해져있거나 탈락으로확정되있는 vertex로 향하는경우 continue
                    g[i] = -1;
                    result_n++;
 
                    continue;
                }
 
                if (hm.get(hm.get(i)) == i) {       // 짝궁인경우 dfs들어갈필요없을거같아서 continue
                    g[i] = 1;
                    g[hm.get(i)] = 1;
 
                    result_n++;
                    result_n++;
                    continue;
                }
 
                P.offer(i);
                dfs(i);
                P.clear();
 
            }
 
            for (int i = 1; i < n + 1; i++) {
                if (g[i] == -1) {
                    result++;
                }
            }
            System.out.println(result);
        }
 
    }
 
    private static void dfs(int x) {
        if (g[hm.get(x)] != 0) {
            int u = P.size();
 
            for (int i = 0; i < u; i++) {
                g[P.poll()] = -1;
                result_n++;
 
            }
 
        } else if (P.contains(hm.get(x))) {        //루프발견
 
            while (!P.isEmpty()) {
 
                int t = P.poll();
 
                if (t != hm.get(x)) {     //루프 시작점이아닌경우 탈락행
                    g[t] = -1;
 
                    result_n++;
                } else {            //루프 발견한경우 전부 뽑아서 팀확정시켜줌
                    int u = P.size();
                    g[hm.get(x)] = 1;
                    result_n++;
 
                    for (int i = 0; i < u; i++) {
                        g[P.poll()] = 1;
                        result_n++;
                    }
 
                }
            }
 
        } else {
            P.offer(hm.get(x));
            dfs(hm.get(x));
 
        }
 
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 관련해서 질문있습니다 ㅠ

anhyunsoo 6년 전 0

zlzmsrhak 6년 전 0

anhyunsoo 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말