JAVA 알고리즘 문제 - k번째 큰 수

설명

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.

현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.

기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.

만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.

 

입력

첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.

 

출력

첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.

예시 입력 1 

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

 

예시 출력 1

143

 

 

전체코드

package com.example.demo;

import java.util.*;

public class Test {
    public static void main(String[] args) {
        // 스캐너로 입력을 받습니다.
        Scanner sc = new Scanner(System.in);

        // 첫 줄에서 N과 K를 입력 받습니다.
        int N = sc.nextInt();
        int K = sc.nextInt();

        // N개의 카드를 입력받기 위한 배열을 생성합니다.
        int[] cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = sc.nextInt();
        }

        // TreeSet을 사용하여 합들을 저장합니다.
        TreeSet<Integer> sumSet = new TreeSet<>();

        // 3중 for문을 사용하여 세 장의 카드를 선택하는 모든 조합을 찾습니다.
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                for (int k = j + 1; k < N; k++) {
                    // 세 장의 카드 합을 sumSet에 추가합니다.
                    int sum = cards[i] + cards[j] + cards[k];
                    sumSet.add(sum);
                }
            }
        }

        // TreeSet은 기본적으로 오름차순 정렬이므로, 큰 값부터 차례대로 확인하기 위해
        // 역순으로 확인합니다. 즉, descendingIterator를 사용합니다.
        int count = 0;
        int result = -1;
        for (int num : sumSet.descendingSet()) {
            count++;
            if (count == K) {
                result = num;
                break;
            }
        }

        // K번째 값을 출력. 만약 K가 존재하지 않으면 -1을 출력합니다.
        System.out.println(result);

        // 스캐너 자원을 해제합니다.
        sc.close();
    }
}

 

 

---

 

 

코드설명

        // 스캐너로 입력을 받습니다.
        Scanner sc = new Scanner(System.in);

        // 첫 줄에서 N과 K를 입력 받습니다.
        int N = sc.nextInt();
        int K = sc.nextInt();

        // N개의 카드를 입력받기 위한 배열을 생성합니다.
        int[] cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = sc.nextInt();
        }

1.입력 받기:

• 첫 번째 줄에서 N과 K를 입력받습니다. 여기서 N은 카드의 개수, K는 우리가 찾고자 하는 K번째로 큰 합입니다.
• 두 번째 줄에서는 N개의 카드 값들을 입력받아 배열에 저장합니다.

 

 

        // TreeSet을 사용하여 합들을 저장합니다.
        TreeSet<Integer> sumSet = new TreeSet<>();

        // 3중 for문을 사용하여 세 장의 카드를 선택하는 모든 조합을 찾습니다.
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                for (int k = j + 1; k < N; k++) {
                    // 세 장의 카드 합을 sumSet에 추가합니다.
                    int sum = cards[i] + cards[j] + cards[k];
                    sumSet.add(sum);
                }
            }
        }

2. 모든 조합의 합 계산:

• 3중 for문을 사용하여 서로 다른 세 장의 카드를 선택하는 모든 경우의 수를 계산합니다.
• 각 조합의 합을 TreeSet에 저장합니다. TreeSet은 값들을 자동으로 정렬해주는 자료구조입니다.

 

 

        // TreeSet은 기본적으로 오름차순 정렬이므로, 큰 값부터 차례대로 확인하기 위해
        // 역순으로 확인합니다. 즉, descendingIterator를 사용합니다.
        int count = 0;
        int result = -1;
        for (int num : sumSet.descendingSet()) {
            count++;
            if (count == K) {
                result = num;
                break;
            }
        }

3. K번째로 큰 값 찾기:

• TreeSet은 기본적으로 오름차순으로 정렬되므로, descendingSet() 메서드를 사용하여 역순으로 값을 탐색합니다.
• 이때, 역순으로 탐색하면서 K번째로 큰 값을 찾고, 이를 출력합니다.

 

 

 

4. 시간 복잡도:

• 3중 for문을 사용하므로 기본적인 카드 수 N에 대해 O(N^3)의 시간이 소요됩니다. 이후 TreeSet에 값을 삽입하고 정렬하는 시간 복잡도는 O(log M)입니다. 여기서 M은 저장된 합의 개수입니다.
• 주어진 N의 범위가 100 이하이기 때문에 해당 알고리즘은 충분히 효율적으로 작동합니다.

 

 

 

---

각 for문의 역할

1. 첫 번째 for문 (i에 해당):
   • i는 첫 번째 카드를 선택하는 인덱스입니다. i의 범위는 0부터 N - 2까지입니다.
     • N - 2까지만 반복하는 이유는 두 번째와 세 번째 카드를 선택할 여유를 두기 위해서입니다.
     • 즉, 첫 번째 카드의 인덱스는 마지막 카드에서 두 번째로 작은 값까지만 선택할 수 있습니다.
   • 예를 들어, 카드 배열이 10개인 경우, i는 0부터 7까지만 선택할 수 있습니다.
2. 두 번째 for문 (j에 해당):
   • j는 두 번째 카드를 선택하는 인덱스입니다. 두 번째 카드는 첫 번째 카드 이후의 카드만 선택해야 하므로 j는 항상 i + 1부터 시작합니다.
     • i + 1은 첫 번째 카드보다 큰 인덱스를 가리키므로 중복되지 않은 두 번째 카드를 선택할 수 있습니다.
   • j의 범위는 i + 1부터 N - 1까지입니다. 세 번째 카드를 선택할 여유를 두기 위해 마지막 카드에서 두 번째까지만 선택할 수 있습니다.
3. 세 번째 for문 (k에 해당):
   • k는 세 번째 카드를 선택하는 인덱스입니다. 세 번째 카드는 두 번째 카드보다 항상 나중에 선택되어야 하므로 k는 j + 1부터 시작합니다.
   • k의 범위는 j + 1부터 N - 1까지이며, 마지막 카드까지 선택할 수 있습니다.

3중 for문이 돌아가는 과정

예시로 카드 5개 (N = 5)를 가지고 있다고 가정해봅시다. 카드 배열은 [1, 2, 3, 4, 5]입니다.

1. 첫 번째 for문 (i):
   • i = 0 (카드 값 1)이 선택됩니다. 이때 i는 0번째 카드를 가리킵니다.
2. 두 번째 for문 (j):
   • 첫 번째 카드가 선택된 상태에서, 두 번째 카드를 선택하는 반복문입니다.
   • j = 1 (카드 값 2)가 선택됩니다. 즉, 첫 번째 카드와 다른 두 번째 카드가 선택되었습니다.
3. 세 번째 for문 (k):
   • 첫 번째와 두 번째 카드를 선택한 상태에서, 세 번째 카드를 선택하는 반복문입니다.
   • k = 2 (카드 값 3)이 선택됩니다. 이때 카드 배열 [1, 2, 3]의 합은 1 + 2 + 3 = 6입니다. 이 합을 TreeSet에 저장합니다.
   • 그 다음, k = 3 (카드 값 4), k = 4 (카드 값 5)가 차례로 선택되면서 각각의 합을 구합니다.
     • k = 3일 때 합은 1 + 2 + 4 = 7
     • k = 4일 때 합은 1 + 2 + 5 = 8
4. 두 번째 카드 반복 (j):
   • j = 2가 될 때, 두 번째 카드는 3이 됩니다. 이제 첫 번째 카드 1, 두 번째 카드 3이 선택된 상태에서 다시 세 번째 카드를 선택합니다.
   • 이때 세 번째 카드는 k = 3 (카드 값 4), k = 4 (카드 값 5)가 됩니다.
     • k = 3일 때 합은 1 + 3 + 4 = 8
     • k = 4일 때 합은 1 + 3 + 5 = 9
5. 첫 번째 카드 반복 (i):
   • 이제 i = 1이 되면 첫 번째 카드 2가 선택됩니다. 다시 두 번째 카드와 세 번째 카드를 선택하는 과정이 반복됩니다.

과정을 요약하면:

• 첫 번째 카드를 고정한 상태에서 두 번째 카드와 세 번째 카드를 선택하는 모든 조합을 구합니다.
• 선택된 세 장의 카드로 조합 가능한 모든 경우의 수를 탐색합니다.
• 각 조합의 합을 계산하여 TreeSet에 저장합니다.

예시 실행 과정

입력 값: N = 5, K = 3, 카드 배열은 [1, 2, 3, 4, 5]입니다.

첫 번째 반복 (i = 0)

• j = 1, k = 2 → 합: 1 + 2 + 3 = 6
• j = 1, k = 3 → 합: 1 + 2 + 4 = 7
• j = 1, k = 4 → 합: 1 + 2 + 5 = 8
• j = 2, k = 3 → 합: 1 + 3 + 4 = 8
• j = 2, k = 4 → 합: 1 + 3 + 5 = 9
• j = 3, k = 4 → 합: 1 + 4 + 5 = 10

두 번째 반복 (i = 1)

• j = 2, k = 3 → 합: 2 + 3 + 4 = 9
• j = 2, k = 4 → 합: 2 + 3 + 5 = 10
  • j = 3, k = 4 → 합: 2 + 4 + 5 = 11

세 번째 반복 (i = 2)

• j = 3, k = 4 → 합: 3 + 4 + 5 = 12

결과적으로 가능한 모든 세 장의 카드 조합을 구하고, 그 합을 TreeSet에 저장합니다. TreeSet을 사용하면 합이 중복되지 않도록 자동으로 처리되며, 모든 합이 오름차순으로 정렬됩니다.