Do it! 알고리즘 코딩 테스트 (22번 ~ 25번)

22번 문제 수 정렬하기 3

---

잘못된 풀이

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));
		
		int n = Integer.parseInt(br.readLine());
		
		LinkedList<Integer> list = new LinkedList<>();
		StringBuffer bf = new StringBuffer();
		for(int i = 0; i < n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list);
		for(int i = 0; i < n; i++) {
			bf.append(list.get(i));
		}
		System.out.println(bf.toString());
	}

}

---

내가 떠올린 풀이 해설

LinkedList로 받아 Collections.sort로 정렬하려고 했는데 메모리 초과가 발생했다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek10989 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] cnt = new int [10001];
		
		
		int n = Integer.parseInt(br.readLine());
		
		StringBuffer bf = new StringBuffer();
		
		for(int i = 0; i < n; i++) {
			cnt[Integer.parseInt(br.readLine())]++;
		}
		br.close();
		
		for(int i = 1; i < 10001; i++) {
			while(cnt[i] > 0) {
				bf.append(i + "\\n");
				cnt[i]--;
			}
			
		}
		System.out.println(bf.toString());
	}
}

---

문제점

sort 를 사용하지 않고 카운팅 정렬을 사용하는 방법이다. 시간 복잡도는 O(N + K)이다. K는 자릿수를 의미하는데 입력 데이터가 K 보다 훨씬 큰 경우. 즉 데이터가 많으면 많을수록O(N)에 가깝기 때문에 이상적으로는 O(N)이라고 보아도 무방하다. 

참고 블로그 : https://st-lab.tistory.com/107

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

---

23번 문제 연결 요소의 개수

---

내가 떠올린 풀이 해설

노드의 최대 개수가 1,000이므로 시간 복잡도는 N^2 이하의 알고리즘을 모두 사용할 수 앗다. 그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다. 방향이 없는 그래프 이므로 양쪽 방향으로 에지를 모두 저장 방문하지 않은 노드가 있는지 확인 후 시작점을 다시 탐색한다.

만약 그래프가 모두 연결되었었다면 DFS는 1번 실행된다.

---

정확한 풀이

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

public class Baek11724 {
	static ArrayList<Integer> arr[];
	static boolean visited[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n + 1];
		visited = new boolean[n + 1];
		for(int i = 1; i < n + 1; i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[e].add(v);
			arr[v].add(e);
		}
		int cnt = 0;
		for(int i = 1; i < n + 1; i++) {
			if(!visited[i]) {
				cnt++;
				DFS(i);
			}
		}
		System.out.println(cnt);
	}

	private static void DFS(int i) {
		if(visited[i]) {
			return;
		}
		visited[i] = true;
		for(int b : arr[i])
		if(visited[b] == false) {
			DFS(b);
		}
	}	
}

---

24번 문제 신기한 소수 찾기

 

---

내가 떠올린 풀이 해설

DFS는 재귀 함수의 형태를 띠고 있다. 자릿수가 두 개인 현재 수 * 10 + a를 계산해 이 수가 소수인지 판단하여 이 수가 소수인지 판단하고 소수라면 재귀 함수로 함수 자릿수를 하나 늘린다. a가 짝수인 경우는 항상 2를 약수로 가지므로 a가 짝수인 경우를 제외한다.

---

정확한 풀이

import java.util.*;
public class Baek2023 {
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		
		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
	}

	private static void DFS(int number, int jarisu) {
		if(jarisu == n) {
			if(isPrime(number)) {
				System.out.println(number);
			}
			return;
		}
		for(int i = 1; i < 10; i++) {
			if(i % 2 == 0) {
				continue;
			}
			if(isPrime(number * 10 + i)) {
				DFS(number * 10 + i, jarisu + i);
			}
		}
	}
	

	private static boolean isPrime(int num) {
		for(int i = 2; i <= num /2; i++) {
			if(num % 2 == 0) {
				return false;
			}
		}
		return true;
	}
}

---

25번 문제 친구 관계 파악하기

---

내가 떠올린 풀이 해설

N의 최대 범위가 2,000이므로 알고리즘의 시간 복잡도를 고려할 때 자유롭다. 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상이면 1 아니라면 0을 출력한다. DFS의 시간 복잡도는 O(V+E)이므로 최대 4,000 모든 노드를 진행했을 때 4000 * 2000이다.

---

정확한 풀이

package DoitCodingTest;
import java.io.*;
import java.util.*;
public class Baek13023 {
	static ArrayList<Integer> arr [];
	static boolean visited[];
	static boolean arrive;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arrive = false;
		
		arr = new ArrayList[n];
		visited = new boolean[n];
		for(int i = 0; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[e].add(v);
			arr[v].add(e);
			
		}
		for(int i = 0; i < n; i++) {
			DFS(i, 1);
			if(arrive) {
				break;
			}
		}
		if(arrive) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
	}

	private static void DFS(int now, int depth) {
		if(depth == 5 || arrive) {
			arrive = true;
			return;
		}
		visited[now] = true;
		for(int i : arr[now]) {
			if(!visited[i]) {
				DFS(i, depth + 1);
			}	
		}
		visited[now] = false;
	}
}

---

오늘의 회고

오늘은 정렬 한 문제와 DFS 문제를 풀어 보았는데 DFS의 개념이 아직 많이 부족한 것 같습니다, 내일은 쉬운 문제에 속하는 DFS문제를 풀어 보겠습니다. 카페에서 공부하다가 오늘부터 스터디 카페로 자리를 옮겼는데 열심히 공부하겠습니다!