BOJ1337

package Silver;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ1337 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 오름차순 정렬
        Arrays.sort(arr);

        int minAddition = Integer.MAX_VALUE;

        // 슬라이딩 윈도우 방식으로 추가되어야 할 최소 원소의 개수 계산
        for (int i = 0; i < arr.length; i++) {   // i는 슬라이딩 윈도우의 시작점
            int count = 1;  // 현재 구간에서 몇 개의 숫자가 같은 구간(5개의 연속된 수)에 속하는지 세는 변수
            for (int j = i + 1; j < arr.length; j++) {  // j는 슬라이딩 윈도우의 끝점
                if (arr[j] - arr[i] < 5) {   // 현재 숫자(arr[j])와 시작점(arr[i])의 차이가 4 이하일 때만 같은 구간에 속하도록 함
                    count++;
                }
            }
            // 5개의 연속된 수가 되기 위해 추가되어야 할 원소의 최솟값을 갱신
            minAddition = Math.min(minAddition, 5 - count);
        }

        // 결과 출력
        System.out.println(minAddition);
    }
}

소감

sort에 대해서 개념을 정립한 후에 백준 문제풀이를 진행했습니다. 문제를 읽고나서 펜을 잡고 문제에 접근한 후 코드를 작성하여 적은 시간이 걸린 것 같습니다.

일정 범위(윈도우)의 데이터를 움직이면서 처리하는 알고리즘 기법인 슬라이딩 윈도우 방식에 대해 새롭게 알게 되었습니다. 추후 배열이나 리스트에서 연속된 구간의 합, 최대/최소값, 특정 패턴 찾기 등의 문제를 해결할 때 적용해볼 생각입니다.