순열 검사 (배열의 정렬과 비교)

출처 ) 프로그래머스

문제 설명

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

제한사항

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

입출력 예 arrresult

[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를 반환하면 됩니다.

반응형

---

 

import java.util.*;
class Solution {
    public boolean solution(int[] arr) {
        boolean answer = true;
        int[] compare = new int[arr.length];
        
        Arrays.sort(arr); //1차적으로 정렬 먼저
        
        for(int i = 0; i < arr.length; i++){
            compare[i] = i+1;    
        }
        
        if(Arrays.equals(compare, arr)){
            answer = true;
        } else {
            answer = false;
        }
        
        return answer;
    }
}

인풋 들어오는 행렬 arr은 분명 원소들이 뒤죽박죽 섞여있을 테니 1~n까지 순서대로 정렬하기 위하여 Arrays.sort

그 다음 새로 비교하기 위한 int형 행렬을 하나 만들어보자.

그리고 새로 비교한 행렬의 0번지에 1, 1번지에 2... 이런식으로 순차적으로 꽂아주자

인풋행렬에서 아다리가 맞지 않고 뭔가 빠진 게 있다면

비교를 위해 만든 compare행렬과 arr행렬을 비교했을때 분명 뻑남.

 

Arrays.sort의 시간복잡도 O(nlogn)

for문을 돌렸을 때 / equal 비교할 때 시간복잡도 각 O(n)

이라서 총 시간복잡도 O(nlogn)