반응형

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
반응형
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
public class Main {
    public static void printArray(int[] a) {
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }
    
    public static int divideArray(int[] a, int head, int tail) {
        int left, right, temp;
        left = head + 1;
        right = tail;
        
        while(true) {
            while(left < tail && a[head] > a[left]) {
                left++;
            }
            
            while(a[head] < a[right]) {
                right--;
            }
            
            if(left >= right) {
                break;
            }
            
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            
            left++;
            right--;
            
        }
        temp = a[head];
        a[head] = a[right];
        a[right] = temp;
        
        return right;
        
    }
    
    public static void sortArray(int[] a, int start, int end) {
        int pivot;
        
        if(start < end) {
            pivot = divideArray(a, start, end);
            
            sortArray(a, start, pivot - 1);
            
            sortArray(a, pivot + 1, end);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        //printArray(a);
        
        sortArray(a, 0, a.length - 1);
        
        printArray(a);
        
    }
}
cs

O(nlogn)의 속도가 평균적이고, 최악에는 O(n^2)의 시간복잡도가 나오기도 한다.

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

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

LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형
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
class StationList{
    public String name;
    public int next;
}
 
 
public class LinkedList {
    public static StationList[] list = new StationList[10];
    
    public static int head;
    
    public static void initStationList() {    
        
        for(int i = 0; i < list.length; i++) {
            list[i] = new StationList();
        }
        
        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;
        
        
        head = 2;
    }
    
    public static void printStationList() {
        int idx = head;
        while(idx != -1) {
            System.out.print("[" + list[idx].name + "] -> ");
            idx = list[idx].next;
        }
        System.out.println();    
    }
    
    public static void insertStationList(int insIdx, String insName, int prevIdx) {
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next;
        list[prevIdx].next = insIdx;
    }
    
    public static void deleteStationList(int delIdx, int prevIdx) {
        list[prevIdx].next = list[delIdx].next;
    }
    
    public static void main(String[] args) {
        initStationList();
        printStationList();
        
        insertStationList(5, "광명", 2);
        printStationList();
        
        deleteStationList(5, 2);
        printStationList();
    }
}
cs

 

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

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

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형

현재 알고리즘 공부를 하고있는데 계속 시간초과가 나서 Scanner를 못쓰게 됐다...

앞으로 많은 문제들이 이러한 제약을 갖고있을 듯 하여 이제서야 공부하게 됐다.

https://spody.tistory.com/60

 

1920번 수 찾기 자바로 풀어 본 짧은 글

1920번 수 찾기 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주

spody.tistory.com

정렬과 이분탐색 모두 사용하는데 시간도 얼마 없는 문제.... 여기서 막혀버렸다

때문에 공부 조금 하고 정리할 겸 올리는 글....

사전준비

1
2
3
4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
cs
1
public static void main(String[] args) throws NumberFormatException, IOException{
cs

main에는 이렇게 IOExcption을 해줘야한다.

BufferedReader는 Scanner에 비해서 속도가 훨씬 빠르다.

이유는 입력된 데이터가 버퍼를 거쳐 전달돼서 데이터 처리 효율이 올라간다.

때문에 데이터가 많이 들어갈 때는 이 클래스를 활용해서 해결해야한다.

또 StringTokenizer를 사용하는 이유는 BufferedReader는 한 줄씩 입력을 받는 readLine을 사용하게 되는데

"10 5 3 1 10" 등 값을 띄어쓰기로 구분 해 입력받는다 이러한 한 줄을 처리하기 위해 String을 token간격으로 끊어 사용한다는 의미의

StringTokenizer를 사용해 해당 값을 처리해준다.

기본적으로 StringTokenizer을 사용하면 띄어쓰기 별로 10 5 3 1 10 이 값에서 nextToken()메소드를 사용할 때마다

순차적으로 꺼낸다.

ex)

1
2
3
4
5
6
7
8
9
10
11
import java.io.BufferedReader;
 
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] a = new int[n];
 
StringTokenizer st = new StringTokenizer(br.readLine());
 
for(int i = 0; i < n; i++) {
    a[i] = Integer.parseInt(st.nextToken());
}
cs

input : 5

           10 5 3 1 10

이 경우

a[0] = token(10)

a[1] = token(5)

a[2] = token(3)

a[3] = token(1)

a[4] = token(10)

이런 식이다.

형태를 잘 기억해두자.

 

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

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

자바 프로젝트를 실행할 때(배포)  (0) 2024.08.18
우테코 프리코스 6기 1주차 숫자야구 회고  (0) 2023.10.26
자바의정석 ch14 람다와 스트림  (0) 2023.09.18
nextInt()입력 후 nextLine()사용 시 주의점  (0) 2022.12.18
반응형

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
반응형
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
class StationList{
    public String name;
    public int next;
    
}
 
public class Main {
    
    public static StationList[] list = new StationList[10];
    
    public static int head;
    
    public static void initStationList() {
        
        for(int i = 0; i < list.length; i++) {
            list[i] = new StationList();
        }
        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;
        
        head = 2;
    }
    
    public static void printStationList() {
        int idx = head;
        while(idx != -1) {
            System.out.print("[" + list[idx].name + "] -> ");
            idx = list[idx].next;
        }
        System.out.println();
    }
    
    public static void insertStationList(int insIdx, String insName, int prevIdx) {
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next;
        list[prevIdx].next = insIdx;
    }
    public static void deleteStationList(int delIdx, int prevIdx) {
        list[prevIdx].next = list[delIdx].next;
    }
    
    public static void main(String[] args) {
        initStationList();
        printStationList();
    
        insertStationList(5, "광명", 2);
        printStationList();
    
        deleteStationList(5,2);
        printStationList();
    }
}
 
cs
반응형
저작자표시 비영리 변경금지

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

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형

알고리즘 정렬기법 중 가장 기본적인 정렬 삽입, 버블, 선택 정렬을 정리했다

시간복잡도는 O(N^2)이고, 익숙해질 때까지 소스를 보면서 눈에 익히고 구현에 대해서도 계속 생각해보자.

선택정렬이 제일 헷갈렸다... 처음엔 제일 쉬워보였는데 어렵네

 

삽입정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 1; i < n; i++) {
            tmp = a[i];
            for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs

 

버블정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            for(j = 0; j < n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
        
    }
}
cs

 

선택정렬

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);
        int tmp = 0;
        int j;
        int index;
        
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            index = i;
            for(j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    index = j;
                    tmp = a[i];
                    a[i] = a[index];
                    a[index] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
이진 탐색  (0) 2023.01.07
반응형

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
반응형

순차적으로 정렬되어있을 때 검색하는 가장 기본적인 검색방식이다.

 

방법은 중간값을 원하는 검색 값과 비교해서 검색하는 방식인데, 작을 땐 범위 아래로 내려서 O(logN) 의 시간복잡도를

갖고있다. 모든 자료를 순차로 탐색하는 것보다 효율이 좋아 자주쓰일 듯 하다.

구현도 쉬운편이고, 효율도 어느정도는 나오기에 구현 방식을 잘 기억해둬야겠다.

간단한 그림 예제와 소스코드 예제를 통해 익혀두기.

그림 예제

이 방식의 핵심은 제일 낮은 인덱스, 제일 큰 인덱스, 중간값 이 세 값을 구하는게 중요한데 중간 값(A[Center])비교를 기준으로 설명하자면

Max : 검색 값이 낮을 때 - Center대입

          검색 값이 높을 때 - 그대로

Min : 검색 값이 낮을 때 - 그대로

         검색 값이 높을 때 - Center대입

Center : 항상 (Min + Max) / 2를 해주면 중간값을 정할 수 있다.

첫번째 구역 나누기
두번째 구역 나누기

 

세번째 구역 나누기
네번째 구역 나누기

마지막 A[0]의 값이 찾는 값과 같다면 "값을 찾았습니다!"

아니라면 "찾는 값이 없어요"가 출력된다.

 

 

소스코드 예제

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[] a = {39, 41, 53, 55, 68, 72, 84, 88, 92, 97, 102};
        
        Scanner sc = new Scanner(System.in);
        
        int b = sc.nextInt();
        int center = 0;
        
        int max = a.length;
        int min = 0;
        
        center = a.length/2;
        
        while(true) {
            if(b == a[center]) {
                System.out.println("값을 찾았습니다!");
                break;
            }
            else if(center == 0) {
                System.out.println("찾는 값이 없어요");
                break;
            }
            else if(b < a[center]) {
                //min 안건드림
                max = center;
                center = (min + max) / 2;
                
                System.out.println("b가 작아 min : " + min + "| max : " + max + "| center : " + center);
            }
            else if(b > a[center]) {
                min = center;
                //max 안건드림
                center = (min + max) / 2;
                
                System.out.println("b가 커 min : " + min + "| max : " + max + "| center : " + center);
            }
        }
    }
}
 
cs

-------------

위에 있는 소스는 23.01.14 다른 문제를 풀다 알게된건데 틀린 예제입니다.

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

일단 간단한 예제를 올리기 전에 고쳐놓기....

요건 제 기준 어려운 예제임당...

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

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

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
반응형

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

+ Recent posts

티스토리툴바