#1337 : 올바른 배열

풀이방법

사용된 것:

정렬

HashSet

 

2022.03.23

오답노트 #1337 : 올바른 배열

 

일단, 전체 배열을 오름차순으로 정렬한다.

 

정렬된 전체 배열을 1~5번째, 2~6번째 ... n-4~n번째 요소의 묶음 순으로 탐색할 것이다.

각 묶음을 탐색하는 방법은 다음과 같다.

 

 

이번에 탐색할 묶음이 아래와 같이 arr[3]~arr[7]이라고 하자.

arr[0]

arr[1]

arr[2]

arr[3]

arr[4]

arr[5]

arr[6]

arr[7]

arr[8]

...

묶음의 첫 번째 요소를 기준값으로 잡는다. 이 경우 arr[3]의 값이 기준값이다.

arr[0]

arr[1]

arr[2]

arr[3]

arr[4]

arr[5]

arr[6]

arr[7]

arr[8]

...

 

 

기준값을 참고하여 아래와 같은 배열을 만든다.

arr[3]

arr[3]+1

arr[3]+2

arr[3]+3

arr[3]+4

만약 arr[3]의 값이 6이라면, {6, 7, 8, 9, 10} 이라는 배열이 만들어지는 것이다.

 

 

 

그 후,

이 두 배열 모두에 들어있는 수의 개수,

즉 겹치는 수의 개수를

int형 변수 cnt에 저장한다.

arr[3]

arr[4]

arr[5]

arr[6]

arr[7]

 

arr[3]

arr[3]+1

arr[3]+2

arr[3]+3

arr[3]+4

 

 

이러한 과정을 1~5번째, 2~6번째 ... n-4~n번째 요소의 묶음에 대하여 모두 수행한다.

그럼 각 묶음마다 cnt가 도출될 것인데, 이 cnt 값들 중 최댓값을 구한다.

 

5에서 (cnt의 최댓값)을 뺀 값을 화면에 출력한다.

 

코드

Java(2022.03.23)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//읽어오기
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for(int i = 0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		//배열을 오름차순 정렬
		Arrays.sort(arr);
		
		//탐색(비교)
		int max_cnt = 1;
		for(int i = 0; i<n; i++) {
			//기준값을 cur에 저장
			int cur = arr[i];
			//cur, cur+1, cur+2, cur+3, cur+4가 저장된 해시셋 hs 만들기
			HashSet<Integer> hs = new HashSet<Integer>();
			for(int j = 0; j<5; j++) {
				hs.add(cur+j);
			}
			
			//배열의 해당 부분과 hs를 비교
			int cnt = 1;
			for(int j = i+1; j<i+5; j++) {
				if(j<n) {
					if(hs.contains(arr[j])) {
						cnt++;
					}
				}
			}
			//cnt 중 최댓값을 max_cnt에 저장
			max_cnt = Math.max(max_cnt, cnt);
		}
		//정답 출력
		System.out.print(5-max_cnt);
	}

}