패스트캠퍼스 챌린지 23일차

다양한 정렬 응용편(Sort Application)

 

수열정렬

 - N개의원소가P배열에 써있는 값으로 이동하여 B라는 배열을 만듬

 

static class Elem implements Comparable<Elem> {
        public int num, idx;

        @Override
        public int compareTo(Elem other) {
            return num - other.num;
        }
    }
}

    static int N;
    static int[] P;
    static Elem[] B;

static void pro() {
        Arrays.sort(B);
        for (int i = 0; i < N; i++) {
            P[B[i].idx] = i;
        }
        for (int i = 0; i < N; i++) {
            sb.append(P[i]).append(' ');
        }
        System.out.println(sb.toString());
}

 

 

 

배열정렬 

 • 정렬은 O(NlogN)

순서대로 읽기 

 • O(N)

  => 시간 복잡도 O(NlogN)

       공간 복잡도 O(N) 

 

카드 알고리즘 구현 (BOJ 20291도 구현해보기)

static void pro() {
        Arrays.sort(a, 1, N + 1);  // Sort
        long mode = a[1];
        int modeCnt = 1, curCnt = 1;  // mode: 최빈값, modeCnt: 최빈값의 등장 횟수, curCnt: 현재 값(a[1])의 등장 횟수

        for (int i = 2; i <= N; i++) {
            if (a[i] == a[i - 1]) {  // a[i] 라는 숫자가 계속 등장하고 있다.
                curCnt++;
            } else {
                curCnt = 1;  // a[i] 라는 숫자가 새롭게 등장했다.
            }

            if (curCnt > modeCnt) {
                modeCnt = curCnt;
                mode = a[i];
            }
        }
        System.out.println(mode);
    }

 

 

 

화살표 함수 구현

 문제파악하기

  - 정답의 최대치 파악

   EX) N = 5000, 점 두개 => 2 * 10^5 만큼의 화살표 길이, 색깔마다 이런 점이 있다면 총 5000/2 쌍 만큼 가능

   즉,모든 점마다 10만 만큼의 길이를 갖는 화살표를 그리는 경우이므로 정답의 최대치 : 5 * 10^8

   => Integer로 계산하여도 된다.

 

 가장 쉬운 방법은 O(N^2) 이므로 최대 시간 값은 100억이 나와 1초(10억)을 넘김으로 다른 방법을 사용

 => 각 점마다, 자신과 가장 가까운 점을 빨리 찾으면 된다(N logN)

 

접근 방법

 1. 같은 색깔의 점들만 모아서 본다

 2. 모은뒤에, 각 점마다 자신과 가장 가까운 것을 찾는다.

 3. 정렬의 특성을 이용하기 위해 점들의 위치를 오름차순으로 정렬 (N logN) 

static int toLeft(int color, int idx) {
     // 샐깔이 color 인 점의 idx 번쨰에 있는 점이 왼쪽으로 화살표를 그린다면
     // 화살표의 길이를 retun 하는 함수, 왼쪽에 점이 없다면 무한대를 return
     
        if (idx == 0)  // 왼쪽에 더 이상 점이 없는 상태
            return Integer.MAX_VALUE;
        return a[color].get(idx) - a[color].get(idx - 1);
    }

    static int toRight(int color, int idx) {
     // 샐깔이 color 인 점의 idx 번쨰에 있는 점이 오른으로 화살표를 그린다면
     // 화살표의 길이를 retun 하는 함수, 오른쪽에 점이 없다면 무한대를 return
     
        if (idx + 1 == a[color].size())  // 오른쪽에 더 이상 점이 없는 상태
            return Integer.MAX_VALUE;
        return a[color].get(idx + 1) - a[color].get(idx);
    }

    static void pro() {
        for (int color = 1; color <= N; color++)
            Collections.sort(a[color]);

        int ans = 0;
        for (int color = 1; color <= N; color++) {
            for (int i = 0; i < a[color].size(); i++) {
                int left_distance = toLeft(color, i); // 왼쪽 점 까지의 거리
                int right_distance = toRight(color, i); // 오른쪽 점 까지의 거리
                ans += Math.min(left_distance, right_distance);
            }
        }
        System.out.println(ans);
    }

 

 

 

23일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]