[코드트리/NOVICE MID] 개발팀의 능력 (JAVA)

🔺 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] arr = new int[5];
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        for(int i = 0 ; i < 5 ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        for(int i = 0 ; i < 5 ; i++) {  // 첫 번째 팀 2명 고르기
            for(int j = i + 1 ; j < 5 ; j++) {
                min = Math.min(min, getDiff(i, j));
            }
        }
        
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
 
    private static int getDiff(int a, int b) {
        int total = 0;
        for(int i : arr) {
            total += i;
        }
 
        int sum1 = arr[a] + arr[b];
        int sum2 = 0;
        int sum3 = 0;
 
        int tmpMin = Integer.MAX_VALUE;
 
        for(int i = 0 ; i < 5 ; i++) {  // 두 번째 팀 2명 고르기
            for(int j = i + 1 ; j < 5 ; j++) {
                if(i == a || i == b || j == a || j == b)    continue; // 같으면 X
                
                sum2 = arr[i] + arr[j];
                sum3 = total - sum1 - sum2;    // 세 번째 팀 1명 = 전체 - 팀1 - 팀2
 
                int[] tmp = {sum1, sum2, sum3};
                Arrays.sort(tmp);
 
                if(sum1 == sum2 || sum2 == sum3 || sum1 == sum3)    continue; // 모든 팀의 능력치가 서로 달라야 함
                tmpMin = Math.min(tmpMin, tmp[2] - tmp[0]);
            }
        }
 
        return tmpMin;
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 먼저 첫 번째 팀에서 2명씩 짝을 짓게 했다.

- 남은 4명에 대해 다시 팀을 구성하게 했다.

- 세 팀의 합을 배열에 저장한 후, 오름차순 정렬했다.

- 모든 팀의 능력치가 다른지 검증한다.

- 가장 큰 값을 가진 팀과 가장 작은 값을 가진 팀의 차이를 구하고, 최솟값과 비교하게 한 후 가장 작은 값을 리턴하게 했다.

- 만약 가장 작은 값이 초기값과 같다면 -1을, 초기값과 다르다면 그대로 출력하게 한다.

 

 

 

---

🔺 다른 풀이들

import java.util.Scanner;
 
public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int MAX_N = 5;
    
    public static int n = MAX_N;
    public static int[] arr = new int[MAX_N];
    public static int totalSum;
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        
        for(int i = 0; i < n; i++)
            totalSum += arr[i];
        
        // 첫 번째 팀원 i와 두 번째 팀원 j, k 고르기
        int minDiff = INT_MAX;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    if(i != j && j != k && i != k)
                        minDiff = Math.min(minDiff, diff(i, j, k));
        
        // 만들 수 없는 경우, 초기값 그대로 남음
        if(minDiff == INT_MAX)
            System.out.print(-1);
        else
            System.out.print(minDiff);
    }
 
    public static int diff(int i, int j, int k) {
        int returnValue = INT_MAX;
    
        int sum1 = arr[i];    // 1인 팀
        int sum2 = arr[j] + arr[k];    // 2인 팀 1
        int sum3 = totalSum - arr[i] - arr[j] - arr[k];    // 2인 팀 2
    
        // 하나라도 합이 같은 팀이 있으면 불가능
        if(sum1 == sum2 || sum2 == sum3 || sum3 == sum1)
            return returnValue;
 
        // 세 팀의 능력 중 최대 - 세 팀의 능력 중 최소
        return Math.max(Math.max(sum1, sum2), sum3) - Math.min(Math.min(sum1, sum2), sum3);
    }
}

 

 

---

💬 느낀 점

빠르게 풀고 싶어요ㅠ

 

1회독	2회독	3회독	4회독	5회독
V