백준 1337번: 올바른 배열

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

 

주어진 N개의 숫자들에 대해서 연속된 5개의 숫자를 만들기 위해 최소 몇개의 숫자를 추가해야하는지 구하는 문제이다. 예를 들어, 3, 5, 7, 10, 18의 경우 4, 6을 넣으면 3, 4, 5, 6, 7이 연속하게 되며 2개의 숫자만 넣으면 되어 최소 추가 조건을 만족한다. N이 50 이하의 자연수 이므로 주어진 숫자들에 대해 만들 수 있는 연속한 구간에 대해 숫자가 있는지 확인하여 있으면 필요한 수가 1개씩 줄어들고 최종 필요한 갯수가 가장 작은 갯수를 출력하였다.

 

 

숫자들을 배열에 받으면서 Set에 저장하였다. 정렬하여 가장 작은 숫자부터 시작하여 연속된 4개의 숫자가 주어진 숫자에 포함되어 있는지 Set의 contains를 이용하여 확인하고 갯수를 센 후, 포함된 숫자의 최대값과 비교하여 최대값을 초기화해준다. 이후, 필요한 숫자의 갯수의 최소값은 (5 - 포함된 숫자의 최댓값)이며 이를 출력하면 된다.

long[] numbers = new long[n];
Set<Long> set = new HashSet<>();
for (int i = 0; i < n; i++) {
    numbers[i] = Long.parseLong(br.readLine());
    set.add(numbers[i]);
}
br.close();
Arrays.sort(numbers);
int max = 1;
for (int i = 0; i < n; i++) {
    long number = numbers[i];
    int count = 1;
    for (long next = number + 1; next < number + 5; next++) {
        if (set.contains(next)) {
            count++;
        }
    }
    max = Math.max(count, max);
}
System.out.print((5 - max));