[문제] 길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다. 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.

제한 조건

  • 배열의 길이는 10만 이하입니다.
  • 배열의 원소는 0 이상 10만 이하인 정수입니다.

입출력 예

arr result
[4, 1, 3, 2] true
[4, 1, 3] false

입출력 예 설명

  • 입출력 예 #1

입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다.

  • 입출력 예 #2

[4, 1, 3]이 주어진 경우, 배열의 길이가 3이므로 배열에는 1부터 3까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3]에는 2가 없고 4가 있으므로 false를 반환하면 됩니다.

풀이

  • 풀이과정
    1. 중복제거, 오름차순 정렬이 핵심이라고 생각. 구글링 후 TreeSet 사용 결정
    2. 입력받는 배열의 크기 만큼 1부터 저장하는 ArrayList를 만든다
    3. 파라미터로 전달된 배열을 중복제거, 오름차순 정렬 한 ArrayList2를 만든다.
    4. ArrayList와 ArrayList2의 값이 완전히 같다면 true를 반환, 아니면 false를 반환
import java.util.*;
class Solution {
	public boolean solution(int[] arr) {
	boolean answer = false;

//		1~갯수 만큼의 배열 생성. e.g. 입력 5,7,4,5,3 -> 1,2,3,4,5 arrlist 생성
	ArrayList<Integer> arrList = new ArrayList<Integer>();
	for(int i=1;i<=arr.length;i++) {
		arrList.add(i);
	}
//		System.out.println("arr1"+arrList);
//		arrlist2 생성 후 중복제거 & 오름차순 
	ArrayList<Integer> arrList2 = new ArrayList<Integer>();
	for(int tmp : arr) {
		arrList2.add(tmp);
	}
	TreeSet<Integer> trr = new TreeSet<Integer>(arrList2);
	arrList2.clear();
	arrList2.addAll(trr);

//		arrList랑 arrList2가 같으면 true 아니면 false
	answer = arrList.equals(arrList2); 
	return answer;
	}
}

결과

  • 정확성: 70.3
  • 효율성: 0.0

문제점?

  • 주어진 테스트 케이스는 모두 통과했는데, 정확성 점수가 떨어지는 이유가 뭔지는 모르겠다
  • 효율성이 빵점나와서 검색해보니 배열을 ArrayList로, ArrayList를 TreeSet으로 바꾸는 과정이 효율적이지 못한 것 같다.
  • 되도록 import 없이 배열 정렬로만 끝내보자
  • TreeSet을 한다고 오름차순정렬이 되는 것이 아니다!!
  • 효율적인 정렬방법 검색

다시풀기 (2019.03.18)

public static boolean arrCheck(int[] arr){
	boolean answer = true;

	Arrays.sort(arr);

	for(int i=0; i<arr.length; i++){
		if(arr[i] != i+1){
			answer = false;
		}
	}

	return answer;
}

참고