자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Hash, sliding window : 시간복잡도 O(n)_K번째 큰 수_TreeSet)

 

 

5. K번째 큰 수

 

예시 입력 1 

10 3
13 15 34 23 45 65 33 11 26 42

예시 출력 1

143

 

 

내가 푼 틀린 풀이

일단 문제를 제대로 이해 못했다.

나는 입력받은 정수배열을 내림차순해서 가장 큰 수 3개를 더하면 되는 줄 알았는데,

그게 아니라 각 정수배열에 있는 값들을 3개 뽑아서 합한 것 들을 내림차순해서 k번째 수에있는 걸 고르는 거였다.

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public int solution(int n , int k, int[] arr) {
        int answer = 0;
        Integer[] integerArr = Arrays.stream(arr)
                .boxed()
                .toArray(Integer[]::new);
        Arrays.sort(integerArr, Comparator.reverseOrder());
        for (int i = 0; i < k; i++) {
            answer += integerArr[i];
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, k ,arr));
    }
}

 

 

강의 풀이 (Time: 211ms Memory: 29MB)

int[]배열 중에 3개를 더하기 위해 3중 포문을 써야 한다.

중복도 제거하고, 정렬도 해주는 TreeSet을 사용했다.

 

• TreeSet<Integer> Tset = new TreeSet<>(); : 오름차순 정렬
• TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder()); : 내림차순 정렬
• Tset.remove(143) : 특정 값을 지우고 boolean값을 리턴
• Tset.size() : 원소의 개수 리턴
• Tset.first() : 오름차순에서는 가장 작은 값, 내림차순에서는 가장 큰 값 리턴
• Tset.last() : 오름차순에서는 가장 큰 값, 내림차순에서는 가장 작은 값 리턴

문제 풀이할때 중복제거한다고 할때 set을 사용하면 됩니다. 정렬되서 중복제거한다고하면 TreeSet을 쓰면 됩니다.

정렬 지원하는 해쉬에는 TreeMap도 있다. 정렬이 필요한 Map을 만들려면 이진트리(레드블랙트리)로 되어있어서 특정 값을 찾으려면 O(logN)의 시간복잡도를 가진다.

import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class Answer {

    public int solution(int n, int k, int[] arr) {
    	// K번째 수가 없다면 -1 리턴하기 위해 초기화
        int answer = -1;
        // Collections.reverseOrder()이 있으면 내림차순, 없으면 오름차순
        TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());

        // n장의 카드에서 3장을 뽑아야 하므로 당연히 3중 포문
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int l = j + 1; l < n; l++) {
                    // 중복값을 제거하고 내림차순으로 정렬하면서 추가된다
                    Tset.add(arr[i] + arr[j] + arr[l]);
                }
            }
        }
        int cnt = 0;
        // Tset에 담긴걸 하나씩 꺼내서 k번째 수를 리턴
        for (int x : Tset) {
            cnt++;
            if (cnt == k) answer = x;
        }
        return answer;
    }

    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, k, arr));
    }
}

 

 

정수 배열을 내림차순 하는 방법 

import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        
        // 배열을 내림차순으로 정렬
        Arrays.sort(arr);
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[n - 1 - i];
            arr[n - 1 - i] = temp;
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        Integer[] arr = {5, 2, 9, 1, 5, 6};
        
        // 배열을 내림차순으로 정렬, 하지만 Integer[]이어야 한다
        Arrays.sort(arr, Comparator.reverseOrder());

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

 

Java에서 for문을 사용하지 않고 배열을 내림차순으로 정렬하려면 Collections.reverseOrder()를 사용하는 방법과 Comparator.reverseOrder()를 사용하는 방법 중 하나를 사용해야 합니다. 이러한 메서드를 사용하려면 배열의 원소가 객체 형태(예: Integer)로 되어 있어야 합니다. 기본 자료형(int, double, char 등) 배열에는 직접적으로 내림차순 정렬을 지원하는 메서드가 없으므로 Arrays.sort()와 같은 방식으로 직접 구현해야 합니다.

// Collections.reverseOrder()
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Integer[] arr = {5, 2, 9, 1, 5, 6};
        
        // 배열을 리스트로 변환
        List<Integer> list = Arrays.asList(arr);
        
        // 리스트를 내림차순으로 정렬
        Collections.sort(list, Collections.reverseOrder());
        
        // 결과 출력
        for (int num : list) {
            System.out.print(num + " ");
        }
    }
}