글 읽기 - 속도 개선 도움 부탁드립니다.

(追記) (追記ここまで)

속도 개선 도움 부탁드립니다.

9466번 - 텀 프로젝트

ygs3004 1년 전 0

리스트, 스택 사용부터 해서 int 배열에 seq 사용하는 형태로까지 변경했는데도 시간초과가 나네요 ᅲᅲ 시간복잡도도 O 인거 같은데 제가 뭔가 잘못 파악하고 있는걸까요?

배열 사용시가 더 빠를것으로 예상했는데 1% 에서 시간초과 바로 나고 ArrayDeque(스택) 사용시 76~78%에서 시간초과 나옵니다

// int[] 배열 사용
import java.io.*;
import java.util.*;
public class Main {
 static BufferedReader br;
 static BufferedWriter bw;
 static boolean[] checked;
 static int result;
 public static void main(String[] args) throws IOException {
 br = new BufferedReader(new InputStreamReader(System.in));
 bw = new BufferedWriter(new OutputStreamWriter(System.out));
 int testCase = Integer.parseInt(br.readLine());
 while(testCase-- > 0) {
 bw.write(String.valueOf(solution()));
 bw.newLine();
 }
 bw.flush();
 bw.close();
 }
 private static int solution() throws IOException {
 int studentNum = Integer.parseInt(br.readLine());
 int[] team = new int[studentNum + 1];
 StringTokenizer st = new StringTokenizer(br.readLine());
 for(int i = 1; i <= studentNum; i++){
 team[i] = Integer.parseInt(st.nextToken());
 }
 checked = new boolean[studentNum + 1];
 result = studentNum;
 for(int i = 1; i <= studentNum; i++){
 if(checked[i]) continue;
 int[] visited = new int[studentNum + 1];
 findTeam(team, i, 0, visited);
 }
 return result;
 }
 private static void findTeam(int[] team, int student, int seq, int[] visited){
 if(checked[student]) return;
 seq++;
 checked[student] = true;
 visited[student] = seq;
 int next = team[student];
 if(visited[next] != 0){
 result -= (seq - visited[next] + 1);
 }else{
 findTeam(team, next, seq, visited);
 }
 }
}
// -------------------------------------------------------------------------------------------
// stack 사용
import java.io.*;
import java.util.ArrayDeque;
public class Main {
 static BufferedReader br;
 static BufferedWriter bw;
 static boolean[] checked;
 static int result;
 public static void main(String[] args) throws IOException {
 br = new BufferedReader(new InputStreamReader(System.in));
 bw = new BufferedWriter(new OutputStreamWriter(System.out));
 int testCase = Integer.parseInt(br.readLine());
 while(testCase-- > 0) {
 bw.write(String.valueOf(solution()));
 bw.newLine();
 }
 bw.flush();
 bw.close();
 }
 private static int solution() throws IOException {
 int studentNum = Integer.parseInt(br.readLine());
 int[] team = new int[studentNum + 1];
 String[] input = br.readLine().split(" ");
 for(int i = 1; i <= studentNum; i++){
 team[i] = Integer.parseInt(input[i-1]);
 }
 checked = new boolean[studentNum + 1];
 result = studentNum;
 ArrayDeque<Integer> stack = new ArrayDeque<>();
 for(int i = 1; i <= studentNum; i++){
 if(checked[i]) continue;
 findTeam(team, i, stack);
 stack.clear();
 }
 return result;
 }
 private static void findTeam(int[] team, int student, ArrayDeque<Integer> stack){
 if(checked[student]) return;
 checked[student] = true;
 stack.push(student);
 int next = team[student];
 if(stack.contains(next)){
 int stackSize = stack.size();
 while (!stack.isEmpty()) {
 if(stack.pop() == next){
 result -= stackSize - stack.size();
 }
 }
 }else{
 findTeam(team, next, stack);
 }
 }
}