백준 23561 - Young 한 에너지는 부족하다.

https://www.acmicpc.net/problem/23561

23561번: Young한 에너지는 부족하다

 

* 문제 요약

대한민국 최고의 스트릿 알고리즘 크루를 찾기 위한 리얼리티 서바이벌 <스트릿 알고리즘 파이터>! 전국에서 알고리즘을 잘한다는 3N 명의 대학생들이 참여했고, 이들은 3명씩 N 개의 크루를 이루어 스트릿 알고리즘 배틀을 벌이게 된다.

하지만 컴퓨터 공학도들은 언제나 혼자 코딩을 해왔기 때문에 제작진이 크루를 만즐어주어야 한다.

제작진은 혹시나 young 한 에너지가 부족한 크루가 생기지 않을 까 걱정하고 있다. 그래서 제작진은 아래와 같은 점을 고려해 N개의 크루를 구성하려고 한다.

- 크루원의 연령의 중간값. 즉, 세 명중 두번째로 연령이 높은 크루원의 연령을 크루의 에너지라 부르자.

- 제작진은 가장 에너지가 높은 크루와 가장 에너지가 낮은 크루의 에너지 차이를 최소화 해야 한다.

최소화한 값을 구하라.

 

* 입력

첫째 줄에 N이 주어진다. 참가자는 총 3N명이다.

둘째 줄에 3N개의 정수가 공백을 사이에 두고 주어진다. i번째 정수 ai는 i번째 참가자의 연령이다.

 

* 출력

3N명의 참가자로 크루 N개를 적절히 구성해, 가장 에너지가 높은 크루와 가장 에너지가 낮은 크루의 에너지 차이를 최소화 했을 때의 에너지 차이 값을 출력하라.

 

* 제한

- 1 <= N <= 100,000

- 1 <= ai <= 100,000,000

 

* 예시

 

* 해결 과정

각 팀에서 나이가 두번째로 많은 사람의 각 팀별 나이차를 최소화 시키려면 전체 참가자 연령을 보았을 때도 평균적인 라인에 들어가는 구간에 존재하는 사람들을 모두 엮어서 각 팀의 두번째로 나이가 많은 사람으로 만들어주면 된다.

그렇게 되면 특정 구간안에 있는 사람들 내부에서 나이가 가장 많은 사람과 가장 적은 사람의 나이 차이를 구해주는 것으로 각 팀에서 나이가 두번째로 많은 사람들의 나이 차이를 최소화 시켜줄 수 있다.

1. 입력받은 값들을 오름차순 정렬한다.

2. 행의 크기는 만들어지는 팀의 숫자, 열의 크기는 3인 2차원 배열을 만들어준다.

3. 2차원 배열에 정렬된 데이터를 순서대로 저장하되, 저장 순서는 위에서 아래쪽으로 내려가는 방향. 즉, 각 열을 기준으로 순서대로 저장해준다. (물론 행을 기준으로 순서대로 저장해줘도 상관없다. 단, 이 때는 2차원 배열의 행의 크기를 3, 열의 크기를 만들어지는 팀의 갯수로 해야 한다.)

4. 반복문을 통해 데이터의 저장이 완료되고 나면 2차원 배열의 두번째 열에 저장되어 있는 데이터들이 전체 참가자들 중 두 번째로 나이가 많은 사람들이 모여있는 구간에 해당되므로, 해당 열의 첫번째 행에 있는 값과 해당 열의 마지막 행에 있는 값의 차이를 구해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int size = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] array = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            array[i] = Integer.parseInt(input[i]);
        }
        Arrays.sort(array);
        int[][] teamArray = new int[size][3];
        int index = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < size; j++) {
                teamArray[j][i] = array[index];
                index++;
            }
        }

        int min = teamArray[0][1];
        int max = teamArray[size - 1][1];
        bw.write((max - min) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 각 반복마다 2차원 배열에서 열 방향으로 (위 -> 아래) 데이터를 저장해준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 최종적으로 2차원 배열의 두 번째 열의 첫번째 행, 두 번째 열의 마지막 행에 있는 값의 차이를 출력해준다.

 

위의 과정을 통해 문제를 해결하였으므로 정렬 및 그리디 알고리즘 문제라고 할 수 있다.