백준 1337 자바 - 올바른 배열 (boj 1337 java)

문제 : boj1337

 

  문제 분류는 정렬과 투 포인터 있긴한데, 내 경우엔 그냥 정렬 없이 그리디로 풀었다. 어떠한 수를 추가할 생각을 하는 것 보다는 그냥 추가해야될게 있던 없던 있다고 치고 해봤을 때, 원래 존재하던게 몇 개 있었는지 확인해 보는 것이 더 간단한 방식일 것이다.

 

  그러니깐 그냥 해당 배열에 있는 값을 HashSet에 모두 넣어서 O(1)로 원하는 수를 찾을 수 있도록 해두고, N개의 수에서 현재 보고 있는 원소의 값을 a라고 하자. 그럼 모든 N개의 a값에 대해 a, a+1, a+2, a+3, a+4를 해시셋에서 확인한다. 그럼 존재하지 않는게 몇갠지 알 수 있다. 그 값 중 가장 작은게 답이다.

 

  예를들어 '예제 입력 4'를 보자.

7
6
1
9
5
7
15
8

  이걸 다음과 같이 구해볼 수 있다. 즉 N개의 입력에 대해 그 뒤로 +4까지 확인해서 원래 존재한 것만 카운팅을 하는 것이다. 그 중 가장 카운팅이 많이된게 답이고, '5-카운팅'한 값이 추가해야 할 최소 수치이니 그걸 출력해주면 된다.

 

  

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        HashSet<Integer> hs = new HashSet<>();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            hs.add(arr[i]);
        }

        int min = 4;
        for (int i = 0; i < n-1; i++) {
            int cnt = 1;
            for (int j = arr[i]+1; j < arr[i]+5; j++) {
                if (hs.contains(j))
                    cnt++;
            }
            min = Math.min(min, 5-cnt);
        }
        
        System.out.println(min);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}