[Java 알고리즘] 백준 2309 일곱난쟁이

[Java 알고리즘] 백준 2309 일곱난쟁이

정답코드:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void findCombination(ArrayList<Integer> dwarfs, int start, int depth, List<Integer> current, List<List<Integer>> result){
        if (depth == 7){
            int sum = 0;
            for (int num : current){
                sum += num;
            }
            if (sum == 100){
                result.add(new ArrayList<>(current));
            }
            return;
        }

        for (int i = start; i < dwarfs.size(); i++){
            current.add(dwarfs.get(i)); // 현재 드워프의 i를 current에 저장한다음,
            findCombination(dwarfs, i+1, depth+1, current, result);
            current.remove(current.size()-1); // 마지막 원소 제거. sum이 100인것을 못찾아서 return 맞고온것.
        }
    }


    public static void main(String[] args) throws IOException {

//        String file = "hdm/src/day3/일곱난쟁이_2309/input.txt";
//        BufferedReader br = new BufferedReader(new FileReader(file));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> sevenDwarfs = new ArrayList<>();

        for (int i = 0; i < 9; i++){
            int input = Integer.parseInt(br.readLine());
            sevenDwarfs.add(input); // [20, 7, 23, 19, 10, 15, 25, 8, 13]
        }
//        System.out.println(sevenDwarfs);

        Collections.sort(sevenDwarfs); // [7, 8, 10, 13, 15, 19, 20, 23, 25]
        List<List<Integer>> result = new ArrayList<>();
        findCombination(sevenDwarfs, 0, 0, new ArrayList<>(), result);

        for (int j = 0; j < 7; j++){
            System.out.println(result.get(0).get(j));
        }



        /*
        난쟁이 7명 x 9명이 나타남.
        난쟁이의 키합은 100.
        아홉 난쟁이의 키가 주어졌을때, 일곱 난쟁이를 찾는 프로그램?

        정답이 여러가지인 경우 아무거나 출력.
        오름차순으로 출력.

         */

    }
}

 

 

코드 설명:

 

리스트 정렬

1. Arrays.sort()

• 사용 대상: 배열에 사용됩니다.
• 예시:

int[] numbers = {5, 2, 8, 1};
Arrays.sort(numbers); // 배열 정렬

2. Collections.sort()

• 사용 대상: List 인터페이스를 구현하는 컬렉션에 사용됩니다. 주로 ArrayList, LinkedList 등에서 사용됩니다.
• 예시:

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
Collections.sort(numbers); // 리스트 정렬

결론

• Arrays.sort()는 배열에만 사용할 수 있습니다.
• Collections.sort()는 List 타입의 컬렉션에 사용할 수 있습니다.

 

3. *result.add(new ArrayList<>(current))*;의 의미:

• current 리스트는 현재 조합을 저장하는 리스트입니다. 이 리스트는 재귀 호출 중에 계속 변경됩니다.
• new ArrayList<>(current)는 current 리스트의 현재 상태를 복사하여 새로운 ArrayList를 생성합니다. 이렇게 함으로써 result에 추가할 때, current의 상태가 변경되더라도 result에는 그 시점의 조합이 고정되어 저장됩니다.
• 만약 그냥 result.add(current);와 같이 작성하면, current 리스트의 참조만 저장되므로, current의 내용이 나중에 변경되면 result에도 반영되어 원하지 않는 결과를 초래할 수 있습니다.

 

4. 심화과정 List<List<Integer>> result가 2차원 배열인 이유:

• result는 여러 개의 조합을 저장하기 위한 리스트입니다. 각 조합은 다시 List<Integer>로 표현됩니다.
• List<List<Integer>>는 리스트 안에 리스트가 들어있는 구조로, 각 내부 리스트는 하나의 조합을 나타냅니다.
• 예를 들어, 만약 조합이 [20, 7, 23], [19, 10, 15] 같은 경우, 이들을 result에 추가하면, 최종적으로 result는 다음과 같은 구조를 갖게 됩니다:

[
  [20, 7, 23],
  [19, 10, 15]
]

 

 

이렇게 하면 모든 조합을 한 곳에 모아두고, 나중에 쉽게 접근하거나 출력할 수 있습니다.

 

따라서, result는 합이 100이 되는 모든 조합을 저장하기 위해 2차원 리스트로 구성된 것입니다.

 

하나의 조합만 찾으면 되는 경우, result 리스트를 사용할 필요가 없습니다. 대신, 조합을 찾으면 바로 출력하거나 해당 값을 반환하면 됩니다.

 

현재 문제는 하나의 조합만 찾아도 인정되기 때문에, 굳이 필요없지만 심화과정이라고 생각하면됨.

 

 

 

Java에서 2차원 배열과 ArrayList의 접근 방식 비교

Java에서 2차원 배열과 ArrayList를 사용하여 데이터를 저장할 수 있습니다. 두 가지 방법은 요소에 접근하는 방식에서 약간의 차이가 있습니다. 이 블로그 포스트에서는 2차원 배열과 ArrayList의 차이점을 간단히 설명하고, 각각의 접근 방식을 비교해보겠습니다.

1. 2차원 배열

2차원 배열은 고정된 크기의 데이터 구조로, 동일한 데이터 타입의 요소를 저장합니다. 배열의 요소에 접근할 때는 인덱스를 사용하여 다음과 같이 호출합니다.

예제 코드

int[][] array = {
    {7, 8, 10},
    {13, 19, 20},
    {23, 25, 30}
};

// 요소 접근
int value = array[1][2]; // 20

위 예제에서 array[1][2]는 20을 반환합니다. 배열은 선언할 때 크기를 정해야 하며, 크기를 변경할 수 없습니다.

2. ArrayList

ArrayList는 가변 크기의 데이터 구조로, 요소를 동적으로 추가하거나 삭제할 수 있습니다. ArrayList에서 요소에 접근할 때는 get() 메서드를 사용해야 합니다.

예제 코드

import java.util.ArrayList;

ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();

ArrayList<Integer> row1 = new ArrayList<>();
row1.add(7);
row1.add(8);
row1.add(10);
arrayList.add(row1);

// 요소 접근
int value = arrayList.get(0).get(2); // 10

위 예제에서 arrayList.get(0).get(2)는 10을 반환합니다. ArrayList는 초기화 후에도 크기를 조정할 수 있으며, 다양한 데이터 타입을 저장할 수 있는 유연성이 있습니다.

결론

• 2차원 배열: 고정된 크기, 빠른 접근 속도, 같은 데이터 타입의 요소 저장.
• ArrayList: 가변 크기, 동적인 데이터 추가/삭제 가능, 다양한 데이터 타입 저장 가능.