반응형

1418번 K-세준수

N까지의 값을 입력받아서 각 수의 소인수분해를 통해 소인수를 받고 해당 소인수의 최댓값을 입력받은 K와 비교해 카운트한 수를 출력

-----

hint

각 소인수를 hashMap에 저장 이후 맥스값 출력

-----

Solution

실행시간 - 3496ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
import java.io.*;
// 1 2 3 4 5 6 7 8 9 10
// 1 2 3 2 5 3 7 2 3 5
class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); 
        int k = Integer.parseInt(br.readLine());
        int[] a = new int[n+1];
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>(n+1);
        
        for(int i = 0; i <= n; i++){
            a[i] = i;
            hs.put(i,0);//해시맵 초기화
        }
        
        //1은 되니까 배제
        for(int i = 2; i <= n; i++){//2부터 n까지의 소인수들을 저장
            int soinsu = a[i];
            for(int j = 2; j <= soinsu; j++){
                while(soinsu % j == 0){ 
                    soinsu /= j;
                    hs.put(i, j);
                }
                // 소인수분해 한 값들중에서 max값을 해당 hs에 집어넣는다.
            }
        }
        
        int count = 0;
        for(int i = 1; i < a.length; i++){
            if(hs.get(i) <= k){
                count++;
            }
        }
        System.out.println(count);
    }
}
cs

직접 무식하게 푼거라 효율이 매우 좋지 않음...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
반응형

24444번 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net

 

이번엔 BFS... DFS 보다 습득하는데 더 오래 걸린 듯 하다

그나마 이번 문제 풀면서 범위설정이나 조건이나 여러가지로 감을 좀 잡은듯

 

------

hint

해당 번호가 몇번째 순서로 도달했는지 저장하는 배열이 따로 필요

------

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    static boolean[] isVisit;
    static ArrayList<Integer>[] a;
 
    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());
        int r = Integer.parseInt(st.nextToken());
 
        int u, v;
 
        isVisit = new boolean[n+1];
        a = new ArrayList[n+1];
 
        for(int i = 1; i < n + 1; i++){
            a[i] = new ArrayList<Integer>();
        }
 
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            a[u].add(v);
            a[v].add(u);
        }
 
        for(int i = 1; i < n + 1; i++){
            if(!a[i].isEmpty()) {
                Collections.sort(a[i]);
            }
        }
 
        BFS(r, n, m);
 
    }
 
    static void BFS(int r, int n, int m){ // r이 1이라고 가정했을 때
        Queue<Integer> queue = new LinkedList<>();
 
        int temp;
        int[] count = new int[n+1];
        int countNum = 1;
 
        isVisit[r] = true;
        count[r] = countNum++;
        queue.offer(r);
 
        while(!queue.isEmpty()){
            temp = queue.poll();
            for(int i = 0; i < a[temp].size(); i++) {
                if (!isVisit[a[temp].get(i)]) {//방문하지 않았을 때 실행
                    isVisit[a[temp].get(i)] = true;
                    count[a[temp].get(i)] = countNum++;
                    queue.offer(a[temp].get(i));
                }
            }
        }
 
        for(int i = 1; i < n + 1; i++){
            System.out.println(count[i]);
        }
    }
}
 
cs

 

실행시간 - 1996ms

너무 길어서 최적화좀 해주고싶은데.... BufferedReader말고는 상상이 안됨

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
반응형

13023번 ABCDE

https://www.acmicpc.net/problem/13023

 

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

 

 

DFS공부하다가 만난 문제 그냥 열심히 구현 하다가

문득 궁금해져서 일반 for문으로 바꾸고 싶어졌었다가 상당히 오랜 시간 잡아먹은 문제

for each에서 for문 가는거 그렇게 어려운 것도 아닌데 중첩이 되어있으니까 좀 헷갈렸던거 같음

 

-------

hint

그냥 dfs구현하고 depth 1에서 5까지 쌓인다면 1을 출력하게 구현하면 됨

-------

Solution

일반 for문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        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());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5 || isDepthFive == 1) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i = 0; i < A[n].size(); i++) {
            if (!visited[A[n].get(i)]) {
                DFS(A[n].get(i), depth + 1);
            }
        }
 
        visited[n] = false;
 
    }
}
 
cs

 

for each문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        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());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i : A[n]) {
            if (!visited[i]) {
                DFS(i, depth + 1);
            }
        }
        visited[n] = false;
    }
}
 
cs

 

처음엔 구현을 못해서 for each로 했는데

일반 for문 구현하고 백준보니까 속도랑 메모리 측면에서 for문이 더 좋았다

그 이유는 chat GPT씨가 설명해줌 ㅎㅎ

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
반응형

11004번 K번째 수

스터디에서 진행한 퀵정렬문제

퀵정렬부턴 구현이 아직 어색해서 힘들었는데, 더 힘들었던건.. 좌측피벗정렬만 고집하다가 시간을 많이 사용했다.

좌측피벗 저격인지 원래 좌측보다 중간이 좋은지 모르겠는데 일단 풀리긴 했음...

 

--------

hint

중간피벗 퀵정렬을 사용하자...

--------

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main{ //중간 피벗 퀵정렬
    //11004 https://www.acmicpc.net/problem/11004
    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 k = Integer.parseInt(st.nextToken());
 
        int[] a = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
 
        //구현부
 
        qSort sort = new qSort();
        qSort.middleQuickSort(a, 0, a.length - 1);
 
        System.out.println(a[k-1]);
 
    }
 
}
 
class qSort{
 
    static void middleQuickSort(int[] a, int left, int right){
        if(left >= right){
            return ;
        }
 
        int pivotIndex = partition(a, left, right);
 
        middleQuickSort(a, left, pivotIndex - 1);
        middleQuickSort(a, pivotIndex, right);
    }
 
    static int partition(int[] a, int left, int right){
        int pivot = a[(left+right) / 2];
        while(left <= right){
            while(a[left] < pivot){
                left++;
            }
            while(a[right] > pivot){
                right--;
            }
            if(left <= right){
                swap(a, left, right);
                left++;
                right--;
            }
        }
        return left;
 
    }
 
    static void swap(int[] a, int b, int c){
        int temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }
}
cs

실행시간 - 1708ms

 

실패한 실행코드(좌측피벗 퀵정렬)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Main{ // 이건 시간초과로 안됨 좌측피벗정렬임.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
 
        int[] a = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
 
        //구현부
        quickSort sort = new quickSort();
        sort.sort(a, 0, a.length-1);
 
        System.out.println(a[k-1]);
//        for (int num:a) {
//            System.out.println(num);
//        }
    }
}
 
class quickSort{
 
    void sort(int[] a, int left, int right){
 
        if(left >= right){ // 스택오버플로우방지
            return ;
        }
 
        int pivot = partition(a, left, right);
 
        sort(a, left, pivot - 1);
        sort(a, pivot + 1, right);
 
    }
 
    int partition(int[] a, int left, int right){
        int pivot = a[left];
        int pivotIndex = left;
        while(left < right) {
 
            while (a[right] > pivot && left < right) {
                right--;
            }
            while (a[left] <= pivot && left < right) {
                left++;
            }
 
            swap(a, left, right);
 
        }
 
        swap(a, pivotIndex, left);
 
 
 
        return left;
    }
 
    void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
cs

 

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
반응형

2164번 카드2

스터디를 시작했는데 거기서 풀기로한 문제중 하나
처음엔 그냥 하던대로 풀었더니 시간초과가 났다.(첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.) 범위가 큼

큐를 사용하는 문젠데 큐를 사용하지 않아서 상당히 비효율적인듯

직접 구현해보고자 했는데 솔직히 감이 안와서 메소드 활용했다.

큐에 있는 기본 메소드 몇개 사용하니까 금방풀림
--------

hint
Queue queue = new LinkedList<>(); 쓰자...

--------

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        Queue<Integer> queue = new LinkedList<>();
        int n = Integer.parseInt(br.readLine());
 
        for(int i = 0; i < n; i++){
            queue.add(i+1);
        }
 
        for(int i = 0; i < n-1; i++) {
            queue.remove();
            queue.add(queue.poll());
        }
        System.out.println(queue.peek());
    }
}
cs

pollFirst메소드도 있는데 이건 생각 못했네
실행시간 - 196ms

 

아래 코드는 실패했던 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Main { // [BOJ] 2164번 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        int length = 0;
        int[] a = new int[n];
        int temp = 0;
 
        for(int i = 0; i < a.length; i++){ // 값 초기화
            a[i] = i+1;
        }
 
        length = a.length - 1;
 
        while(length > 1){//index가 0이 될때까지
            temp = a[1];
            for(int i = 0; i < length-1; i++){
                a[i] = a[i+2];
            }
            length--;
            a[length] = temp;
        }
        System.out.println(temp);
    }
}
//시간초과 코드
cs

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
반응형

24060번 알고리즘 수업 - 병합정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1 (acmicpc.net)

 

24060번: 알고리즘 수업 - 병합 정렬 1

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

www.acmicpc.net

 

진짜 미친문제.... 의사코드 따라해서 겨우한거같은데 또 이걸 제대로 하지도 못함...
이건 아직도 잘 모르겠다...

다른 알고리즘 책에서 병합정렬 배운거 그대로 구현해서 해봤는데 실패하고 아직 구조이해가 부족한듯?

의사코드 따라해도 안돼서 그냥 참고해서 마무리했다.

정말 머리가 못따라가나... ㅜㅜ
--------


hint - 의사코드가 도움되긴 함


--------

실패한 병합정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Main {
    
    static int[] buff = new int[500000];
    static int count = 0;
    static int searchCount = 0;
    static int setResult = -1;
    
    static void merge_sort(int[] a, int left, int right) { // 그냥병합정렬
        if(left < right) {
            int center = (left + right) / 2;
            int p = 0;
            int i;
            int j = 0;
            int k = left;
            merge_sort(a, left, center);
            merge_sort(a, center + 1, right);
            
            //1)배열의 앞부분(a[left] ~ a[center])을 
            //buff[0] ~ buff[center - left]에 복사합니다.
            //for문이 끝날 때 p의 값은 복사한 요소의 개수 center - left + 1이 됩니다.
            for(i = left; i <= center; i++) {
                buff[p++] = a[i];
            }
            
            // 2)배열의 뒷부분(a[center + 1] ~ a[right])과 
            //buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 b에 저장합니다.
            while(i<=right && j < p) {
                if(buff[j] <= a[i]) {
                    if(count == searchCount) {
                        setResult = buff[j];
                    }
                    System.out.println("현재 수 : " + buff[j]);
                    a[k++] = buff[j++];
                    count++;
                }
                else {
                    if(count == searchCount) {
                        setResult = a[i];
                    }
                    System.out.println("현재 수 : " + a[i]);
                    a[k++] = a[i++];
                    
                    count++;
                }
            }
            
            
            // 3)배열 buff에 남아있는 요소를 배열 a에 복사합니다.
            while(j < p) {
                if(count == searchCount) {
                    setResult = buff[j];
                }
                System.out.println("현재 수 : " + buff[j]);
                a[k++] = buff[j++];
                count++;
            }
            
        }
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrayN = Integer.parseInt(st.nextToken());
        
        searchCount = Integer.parseInt(st.nextToken());
        
        int[] array = new int[arrayN];
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < arrayN; i++) {
            array[i] = Integer.parseInt(st1.nextToken());
        }
 
        merge_sort( array, 0, arrayN-1); // 이게 진짜 병합정렬
 
        bw.write(Integer.toString(setResult) + " ");
        bw.write(Integer.toString(count));
        
        bw.flush();
        bw.close();
        
    }
}
cs

망했던 반례 :

8 9
1 2 3 4 5 6 7 8

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    
    static int[] buff = new int[500001];
    static int count = 0;
    static int searchCount = 0;
    static int setResult = -1;
 
    
    static void merge_sort(int a[], int p, int r) {
        if(p < r) {
            int q = (p + r) / 2;
            merge_sort(a, p, q);
            merge_sort(a, q + 1, r);
            merge(a, p, q, r);
        }
    }
    
    static void merge(int a[], int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int t = p;
        
        while(i <= q && j <= r) {
            if(a[i] <= a[j]) {
                buff[t++] = a[i++];
            }
            else {
                buff[t++] = a[j++];
            }
        }
        
        while(i <= q) {
            buff[t++] = a[i++];
        }
        while(j <= r) {
            buff[t++] = a[j++];
        }
        
        i = p;
        while(i<= r) {
            a[i] = buff[i++];
            if(++count == searchCount){
                System.out.println(a[i-1]);
                System.exit(0);
            }
        }
    }
    
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrayN = Integer.parseInt(st.nextToken());
        
        searchCount = Integer.parseInt(st.nextToken());
        
        int[] array = new int[arrayN];
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < arrayN; i++) {
            array[i] = Integer.parseInt(st1.nextToken());
        }
 
        merge_sort( array, 0, arrayN - 1); // 이게 진짜 병합정렬
 
        bw.write(Integer.toString(setResult));
        
        bw.flush();
        bw.close();
        
    }
}
cs


실행시간 - 720ms

 

언젠가 재도전 해보자...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
반응형

1920번 수 찾기

1920번: 수 찾기 (acmicpc.net)

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

첫째줄 n입력
둘째줄 n갯수 입력
셋째줄 m입력
넷째줄 m갯수 입력

m이 n에 있는지 탐색 후 1(true) 0(false)출력

일단 그냥 구현했을 때 실패했음 원인은 시간초과

알고리즘쪽 보니까 이분탐색하는 부분이 있더라...
이분탐색 구현해보고있는데 배열로 탐색하는 버전은 너무 어색하더라...
내일 for문으로 다시 구현해봐야할듯

for문 통해서 이분탐색 했는데 nextint로는 속도가 안나옴. 또 첫 구현에서는 탐색하는 수들도 전부 배열로 넣어서그런지
시간이 압도적으로 부족한 느낌이 들었음...
때문에 결국 bufferedReader, StringTokenizer를 사용해서 입출력속도를 많이 올렸다.

이제부턴 무조건 써야하나... 타입에 익숙해져야할듯
실버 4 문제인데 이틀을 썼다... 그래도 풀었을 때 상당히 기뻤음.
시간초과 -> 출력초과 -> 틀렸습니다 무한반복... 이분탐색 구현에 자꾸 빼먹는게 생겨서 그런가 참 힘들었다...
반례찾는것도 어렵고... 본인이 반례를 생각하려 노력해야하는데 쉽지않음
탐색이 주 문제니까 sort는 그냥 array.sort를 사용했고, 탐색을 직접 구현해봤다. 이분탐색 어려워징징징

--------

hint
이분탐색을 잘 구현해내면 된다.
내가 헷갈린 부분은 시간이 중요하니까
처음엔 배열 두개를 만들었는데
두개 만들 필요가 없는 걸 잘 생각해서 하면 될듯

--------


solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] a = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        int left;
        int right;
        int center;
        
        long key = 0;
        int isTrue = 0;
        
        for(int i = 0; i < m; i++) {
            key = Integer.parseInt(st.nextToken());
            left = 0;
            right = a.length - 1;
            center = right / 2;
            isTrue = 0;
            while(left <= right) {
                if(a[center] == key) {
                    System.out.println("1");
                    isTrue = 1;
                    break;
                }
                else if(a[center] > key) {
                    right = center - 1;
                    center = (left + right) / 2;
                }
                else if(a[center] <key) {
                    left = center + 1;
                    center = (left + right) / 2;
                }
                
            }
            if(isTrue == 0) {
                System.out.println("0");
            }
        }
    }
}
cs



실행시간 - 1272ms (이거맞냐....) 자바라 봐준거같은데 sort 직접 구현했으면 시간초과 걸렸을듯

약 2일 소요.... ㅜㅜㅜㅜ 실버가 이런데 더 올라갈 수 있을까...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
반응형

1427번 소트인사이드

1427번: 소트인사이드 (acmicpc.net)

 

1427번: 소트인사이드

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

내림차순정렬.
수를 붙여서 준다
그러면 그걸 스플릿으로 잘라서 비교 후 내림차순정렬해보자
int형으로 바로 바꾼 후에 자리수별로 자르는거는 너무 지저분해보일까봐 안하고
String으로 입력받은 후 형변환을 통해 int배열에 입력 이후 비교정렬 실행했다.

--------
hint
Character.getNumericValue(charArray[i])를 활용한 int배열 등록

 

 

---------
solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String N = sc.nextLine();
        int temp;
        
        
        int length = N.length();
        char[] charArray = new char[length];
        int[] b = new int[length];
        
        for(int i = 0; i < N.length(); i++) {
            charArray[i] = N.charAt(i);
        }
        
        for(int i = 0; i < N.length(); i++) {
            b[i] = Character.getNumericValue(charArray[i]);
        }
        for(int j = 0; j < N.length(); j++) {
            for(int i = 0; i < N.length()-1; i++) {
                if(b[i] < b[i+1]) {
                    temp = b[i];
                    b[i] = b[i+1];
                    b[i+1] = temp;
                }
            }
        }
        for(int i = 0; i < N.length(); i++) {
            System.out.print(b[i]);
        }
    }
}
cs


실행시간 - 208ms
정렬을 다른기법을 쓰면 더 좋겠지만 아직 안됨. 직접 내 손으로 구현하는것이 현재목표
일부러 정렬관련 메서드는 사용하지않았다..

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
반응형

2563번 색종이

2563번: 색종이 (acmicpc.net)

 

2563번: 색종이

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록

www.acmicpc.net

다차원배열 단계에서 나온 색종이다.

가로세로어쩌구... 다차원 배열을 사용하라해서 배열에 0값에서 칠한것만 1로 바꾸고 하는 방식
중복되는 곳은 안바꾸면 그만 나중에 넓이출력은 전체탐색으로 1의 값을 갖고있는 것만 카운트하면될듯?

색종이의 수는 100이하 = 100개의 배열생성 후 쭉 추가하면될듯? 필요없을수도있고

일단 색종이의 넓이는 정사각형으로 한변이 10짜리다.즉 좌표값을 얻고 해당 좌표에서 +10까지 1을 넣어주면 된다.

hint
for(int j = x[i]; j < x[i]+10; j++) // 가로x축
for(int g = y[i]; g < y[i]+10; g++) // 세로y축값
색종이의 길이만큼만 1로 채우기

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[][] a = new int[100][100];
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int count = 0;
        int[] x = new int[n];
        int[] y = new int[n];
        
        for(int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n; i++) { // n번 색칠하는거에 의미가 있는 for문
            
            for(int j = x[i]; j < x[i]+10; j++) { // 가로x축
                for(int g = y[i]; g < y[i]+10; g++) { // 세로y축값
                    if(a[j][g] == 0) {
                        a[j][g] = 1;
                    }
                }
            }
        }
        
        for(int i = 0; i < 100; i++) {
            for(int j = 0; j < 100; j++) {
                if(a[i][j] == 1) {
                    count++;
                }
            }
        }
        
        System.out.println(count);
    }
}
cs


실행시간 - 224ms

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 17478번 재귀함수가 뭔가요? 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
반응형

17478번 재귀함수가 뭔가요?

악명높은 재귀함수가 시작됐다...
지식인분들의 추천으로 정렬 전에 재귀함수를 하라하셔서 재귀부터 뿌셔보고 정렬을 다시 정복하려한다.
수 정렬하기는 브론즈1이였는데 이왜실5?

재귀횟수 1<=N<=50
재귀횟수에 따른 챗봇의 응답을 출력
ㅋㅋㅋㅋㅋ출력이 웃기다 근데 저걸 어케 구현하지?

일단 메서드부터 만들어서 Depth에 따른 출력값을 정해보자...

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

까지가 기본 출력값이라 생각된다.
이걸 함수 depth에 따라 나눠야하는데 위치가 중요할 것이다. 잘 고민해서 넣어보자

--------


hint
1depth당 ____(언더바임 사이드바 아님)이 들어간다. 참고해서 잘 보자

재귀하는 부분을 기준으로 위 아래로 나뉜다.

 

위

----

아래

이후 마지막 depth에 정답 호출과 첫 값 출력에 잊지말자.

--------

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Scanner;
 
public class Main {
        static int repeatn;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        repeatn = n;
        
        myrepeat(0, n);
    }
    
    public static void myrepeat(int num, int n) {
        String s = "____";
        if(n >= 0) {
            for(int i = 0; i < num; i++) {
                System.out.print(s);
            }
            System.out.println("\"재귀함수가 뭔가요?\""); // s.repeat() 이건 자바11에서만사용
            if(n != 0) {
            
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
                
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
                
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
            }
            
            myrepeat(num+1,n-1);
            
            if(n == 0) {
                for(int i = 0; i < num; i++) {
                    System.out.print(s);
                }
                System.out.println("\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            }
            
            for(int i = 0; i < num; i++) {
                System.out.print(s);
            }
            
            if(num == 0) {
                System.out.println("라고 답변하였지.");
            }else {
                System.out.println("라고 답변하였지.");
            }
        }
    }
}
cs

 


실행시간 - 332ms

머릿속에서 한번에 생각해서 구현은 참.... 어렵다...
하다가 포기하고 구현하면서 생각 계속한거같다
결국 재귀함수에 두개의 정수를 입력받아야 구현이 됐다...
이것도 역시 깔끔하지 못해 아쉽지만 지금은 구현에 만족!!!

ps. 오타도 복붙해서 없고 문제될게 없는데 했는데... 하이픈(-)이 아니라 언더바(_)였다.... 아니 저거 누가봐도 띄엄띄엄 있어서 하이픈인줄.....

이거때문에
시간을 얼마나 먹은건지... 문제의 조건을 잘 봐야한다는 것을 이번에도 또 느끼게 됐다...

또, 조건에서 언더바말고도 마지막에 \n들어가는게 문제인가 해서 해당 조건도 추가해놨는데 그 부분은 문제가 없었다.

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05
백준 10989번 수 정렬하기 자바로 풀어 본 짧은 글  (0) 2022.12.29
백준 2798번 블랙잭 자바로 풀어 본 짧은 글  (0) 2022.12.27
백준 2292번 벌집 자바로 풀어 본 짧은 글  (0) 2022.12.20

+ Recent posts

티스토리툴바