[Java] SWEA 5643 키 순서

5643 키 순서 문제 링크

#1

package week03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class SWEA_5643 {
	static int N;
	static int M;
	static int[][] node;
	static boolean[] visited;
	static boolean[] visited2;
	static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> result2 = new ArrayList<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			
			node = new int[N+1][N+1];
			
			StringTokenizer st;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				// 각 i에 아래 노드에 해당하면 1 저장
				node[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
			}
			
			visited = new boolean[N+1];
			visited2 = new boolean[N+1];
			for(int i=0; i<=N; i++) {
				result.add(new ArrayList<Integer>());
				result2.add(new ArrayList<Integer>());
			}
			
			
			for(int i=1; i<=N; i++) {
				findMinNode(i);
				findMaxNode(i);
			}
			
			
			int answer = 0;
			for(int i=1; i<=N; i++) {
				if(result.get(i).size() + result2.get(i).size() == N-1) {
					answer++;
				}
			}
			
			System.out.println("#"+t+" "+answer);

		}
	}
	
	public static void findMinNode(int x) {
		if(visited[x]) return;
		
		
		for(int i=1; i<=N; i++) {
			if(node[x][i] == 1 && !result.get(x).contains(node[x][i])) {
				result.get(x).add(i);
				if(!visited[i]) {
					findMinNode(i);
				}
				for(int j=0; j<result.get(i).size(); j++) {
					if(!result.get(x).contains(result.get(i).get(j))) {
						result.get(x).add(result.get(i).get(j));
					}

				}
			}
		}
		
		visited[x] = true;
	}
	
	public static void findMaxNode(int x) {
		if(visited2[x]) return;
		
		for(int i=1; i<=N; i++) {
			if(node[i][x] == 1 && !result2.get(x).contains(node[i][x])) {
				result2.get(x).add(i);
				if(!visited2[i]) {
					findMaxNode(i);
				}
				for(int j=0; j<result2.get(i).size(); j++) {
					if(!result2.get(x).contains(result2.get(i).get(j))) {
						result2.get(x).add(result2.get(i).get(j));
					}

				}
			}
		}
		visited[x] = true;
	}
}

• 시간 초과가 날 것 같긴 했다..
• 메모리랑 시간 둘 다 엄청 쓰고 있어서 통과가 무리일 것 같긴 했어..

#2

package week03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class SWEA_5643 {
	static int N;
	static int M;
	static int[][] node;
	static boolean[] visited;
	static boolean[] visited2;
	static HashSet<Integer>[] result;
	static HashSet<Integer>[] result2;
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			
			node = new int[N+1][N+1];
			
			StringTokenizer st;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				// 각 i에 아래 노드에 해당하면 1 저장
				node[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
			}
			
			visited = new boolean[N+1];
			visited2 = new boolean[N+1];
			result = new HashSet[N+1];
			result2 = new HashSet[N+1];
			for(int i=0; i<=N; i++) {
				result[i] = new HashSet<>();
				result2[i] = new HashSet<>();
			}
			
			for(int i=1; i<=N; i++) {
				findMinNode(i);
				findMaxNode(i);
			}
			
			
			int answer = 0;
			for(int i=1; i<=N; i++) {
				if(result[i].size() + result2[i].size() == N-1) {
					answer++;
				}
			}
			
			System.out.println("#"+t+" "+answer);
		}
	}
	
	public static void findMinNode(int x) {
		if(visited[x]) return;
		
		for(int i=1; i<=N; i++) {
			if(node[x][i] == 1 && !result[x].contains(i)) {
				result[x].add(i);
				if(!visited[i]) {
					findMinNode(i);
				}
				result[x].addAll(result[i]);
			}
		}
		visited[x] = true;
	}
	
	public static void findMaxNode(int x) {
		if(visited2[x]) return;
		
		for(int i=1; i<=N; i++) {
			if(node[i][x] == 1 && !result2[x].contains(i)) {
				result2[x].add(i);
				if(!visited2[i]) {
					findMaxNode(i);
				}
				result2[x].addAll(result2[i]);
			}
		}
		visited2[x] = true;
	}
}

• 진짜 어디가 문제인지 모르겠어서 gpt 도움을 살짝 받음..
  
  
• 처음에 HashSet 자료형을 쓰려다가 HashSet 자료형에서 요소 하나를 빼는 방법이 없어서 ArrayList를 사용한 거였는데
• HashSet.addAll(HashSet); 하니까 요소 하나를 꺼낼 필요가 없어졌음
  
  
• !result.get(x).contains(node[x][i]) 아니 이거.. node[x][i]이면 항상 0아니면 1임..
• result.get(x)에 0이나 1이 있는 지를 왜 확인하는데..
• 내 의도는 !result.get(x).contains(i)이게 맞음
  
  
• 이것저것 계속 수정해보긴 했는데
• 결과적으로,
• ArrayList 사용하다보니까 contains를 여러 번 사용하게 되는 게 가장 큰 문제였던 거 같음
• 다른 수정사항 지우고 다시 돌려봤는데 그것도 통과됨..