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 [자바]
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. ww..
st-lab.tistory.com
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문제를 풀어 보겠습니다. 카페에서 공부하다가 오늘부터 스터디 카페로 자리를 옮겼는데 열심히 공부하겠습니다!
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| Do it! 알고리즘 코딩 테스트 (26번 ~ 28번) (0) | 2022.05.26 |
|---|---|
| 백준)DFS (0) | 2022.05.25 |
| Do it! 알고리즘 코딩테스트(16번 ~ 20번) (0) | 2022.05.23 |
| 백준) 수학, 좌표정렬 (0) | 2022.05.21 |
| Do it! 알고리즘 코딩테스트(14번) (0) | 2022.05.20 |
