문제 : 길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있으면 true, 없으면 false를 반환하기

제한사항 : 배열의 길이는 10만이하, 배열의 원소는 0이상 10만 이하인 정수

 

풀이 : binarySearch라는 탐색 알고리즘을 사용하여 풀었다.

binarySearch를 사용하려면 탐색할 배열을 정렬해야 한다.

그래서 매개변수로 받은 배열을 정렬한 뒤, 해당 인덱스에 해당 숫자가 없으면 false를 반환하자고 생각했다.

 

처음엔 자바에서 제공하는 Arrays.sort()이라는 함수를 사용해서 배열을 정렬했다.

이 후, binarySearch라는 표준라이브러리를 사용하여, 배열에 포함이 되지 않는 수를 넣으면 음수로 돌려주고 false로 리턴하도록 해줬다.

Arrays.binarySearch(배열,값)은 배열안에 찾고자하는 값이 존재하면 해당 값의 인덱스를 반환해주고, 없으면 배열에 포함되지 않았다는 의미로 음수를 반환해준다.

 

/***************************************************
 20200514 JAVA 개발 TYPE A 2번
 ***************************************************/
import java.util.Arrays;

public class Duplication {
    public boolean duplication(int[] arr) {
        boolean answer = true;
        int result = 0;
        Arrays.sort(arr); // 매개변수로 받은 인트형 배열을 정렬한다
        for (int i = 1; i <= arr.length; i++) {
            result = Arrays.binarySearch(arr, i); // 이진검색 표준라이브러리 사용하여 검색한 후, i의 위치를 반환한다.
            // binarySearch 는 정렬되어 있는 배열만 사용가능함
            if (result < 0) {
                answer = false;
                break;
            }
        }
        return answer;
    }
}