[SWEA] 5948 새샘이의 7-3-5 게임

: 7개의 서로 다른 수 중에서 3개를 골라 합을 구하는데 이 합 중에서 5번째로 큰 수를 출력해야 한다.

: 중복된 수는 같은 하나로 처리되어야 하기 때문에 HashSet을 사용해야 겠다는 생각이 들었다.

: 여러개의 값중에서 특정 개수의 수를 골라 그 합을 알아내야 하기 때문에 조합을 생각해볼 수 있다.

 

1. 테스트 케이스의 수를 T에 입력받는다.

2. 입력받은 수를 arr에 넣는다.

3. 입력받은 수들의 합을 저장할 HashSet sum을 만든다.

4. 재귀함수 getSum을 만든다.

: 각각의 수를 포함하는 경우, 포함하지 않는 경우로 나눠 함수를 다시 호출해준다.

: 만약 배열을 모두 순회했고, 선택한 수가 3개라면 핪한 값을 sum이라는 HashSet에 넣어준다.

5. main으로 돌아와 5번째로 큰 수를 구하기 위해 HashSet을 Array로 바꿔서 Arrays.sort() 메소드를 사용하여 정렬시킨다.

6. 다섯번째로 큰 수는 배열의 사이즈에서 -5한 index에 위치해 있으므로 해당번째를 출력에 넣어준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static HashSet<Integer> sum;
    static int[] arr;
    public static void main(String[] args) throws NumberFormatException, IOException {
        // 테스트 케이스 수 입력
        int T = Integer.parseInt(br.readLine());
         
        for(int tc = 1; tc <= T; tc++) {
            // 숫자들을 배열로 입력 받음
            String[] tmp = br.readLine().split(" ");
            arr = new int[tmp.length];
            for(int i = 0; i < tmp.length; i++)
                arr[i] = Integer.parseInt(tmp[i]);
            sum= new HashSet<>();
            getSum(0,0,0);
            Object[] newArray = sum.toArray();
            Arrays.sort(newArray);
            sb.append("#" + tc + " " + newArray[sum.size()-5] + "\n");
        }
        System.out.println(sb);
         
    }
    static void getSum(int idx, int cnt, int total) {
        if(idx == arr.length) {
            if(cnt == 3)
                sum.add(total);
            return;
        }
        getSum(idx+1, cnt + 1, total+arr[idx]);
        getSum(idx+1, cnt , total);
    }
}