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

백준 - 일곱 난쟁이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class baekjoon_2309 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] people = new int[9];
        for (int i = 0; i < 9; i++) {
            int height = Integer.parseInt(br.readLine());
            people[i] = height;
        }

        boolean[] visited = new boolean[9];
        ArrayList<Integer> list = new ArrayList<>();
        backTracking(people, visited, list);
    }

    private static void backTracking(int[] people, boolean[] visited, ArrayList<Integer> list) {
        if (list.size() == 7) {
            if (list.stream().mapToInt(Integer::intValue).sum() == 100) {
                Collections.sort(list);
                for (int height : list) {
                    System.out.println(height);
                }
                System.exit(0);
            }
            return;
        }

        for (int i = 0; i < 9; i++) {
            if (!visited[i]) {
                visited[i] = true;
                list.add(people[i]);
                backTracking(people, visited, list);
                list.remove((Integer)people[i]);
                visited[i] = false;
            }
        }
    }
}

예전에 브루트포스로 풀었었는데 백트랙킹으로 풀어보았다.

ArrayList를 사용했다. ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트이다. ArrayList는 객체들이 추가되어 저장 용량을 초과하면 자동으로 저장 용량이 늘어난다.

ArrayList를 정렬할때는 Collections.sort();를 사용한다.
ArrayList 정렬

ArrayList에서 remove를 할때 인자에 숫자를 넣으면 해당 인덱스의 값이 삭제되고, 객체를 넣으면 해당 객체가 삭제된다. 따라서 숫자 값을 삭제하고 싶을 때는 Wrapper Class를 이용해줘야한다.

list.remove((Integer)people[i]);

ArrayList remove

ArrayList의 합을 구하기 위해 stream을 다음과 같이 사용했다.

list.stream().mapToInt(Integer::intValue).sum()

System.exit(0);으로 강제종료 하였다.

나중에 다시 풀어볼떄 index를 이용해서 매번 0~9번까지 탐색이 아니라 다음 인덱스만 탐색하게 해보자.