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

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] arr = new int[6];
    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 < 6 ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 2명씩 3팀
        for(int i = 0 ; i < 6 ; i++) {  // 1번째 팀원
            for(int j = i + 1 ; j < 6 ; j++) {
                min = Math.min(min, getDiff(i, j));                
            }
        }
 
        System.out.println(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 < 6 ; i++) {  // 2번째 팀원
            for(int j = i + 1 ; j < 6 ; j++) {
                if(i == a || i == b || j == a || j == b)    continue;   // 같으면 안 됨
 
                sum2 = (arr[i] + arr[j]);
                sum3 = total - sum1 - sum2;
 
                int[] arr = {sum1, sum2, sum3};
                Arrays.sort(arr);
 
                int diff = arr[2] - arr[0]; // 가장 큰 팀과 작은 팀의 차이 구하기
                tmpMin = Math.min(tmpMin, diff);
            }
        }
 
        return tmpMin;        
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

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

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

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

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

 

 

 

---

🔺 다른 풀이들

import java.util.Scanner;
 
public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int MAX_N = 6;
    
    public static int n = MAX_N;
    public static int[] arr = new int[MAX_N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        
        // 첫 번째 팀원 만들기
        int minDiff = INT_MAX;
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                
                // 두 번째 팀원 만들기
                for(int k = 0; k < n; k++)
                    for(int l = k + 1; l < n; l++) {
                        //첫 번째 팀원과 두 번째 팀원이 겹치면 안 됨
                        if(k == i || k == j || l == i || l == j)
                            continue;
 
                        minDiff = Math.min(minDiff, diff(i, j, k, l));
                    }
        
        System.out.print(minDiff);
    }
 
    public static int diff(int i, int j, int k, int l) {
        int totalSum = 0;
        for(int idx = 0; idx < n; idx++)
            totalSum += arr[idx];
        
        // 세 번째 팀원의 합 = 전체 - 첫 번째 팀원 - 두 번째 팀원의 합
        int sum1 = arr[i] + arr[j];
        int sum2 = arr[k] + arr[l];
        int sum3 = totalSum - sum1 - sum2;
        
        // 세 팀의 차이 중 "최댓값" 리턴
        int ret = Math.abs(sum1 - sum2);
        ret = Math.max(ret, Math.abs(sum2 - sum3));
        ret = Math.max(ret, Math.abs(sum3 - sum1));
        
        return ret;
    }
}

 

 

---

💬 느낀 점

어렵지 않은데 은근 시간이 걸림...

푸는 시간을 줄이자!

 

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