JAVA(2022.07.21) - 알고리즘 문제 해설<순열검사>

문제 설명

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

 

 나의 코드)

class Solution {
    public boolean solution(int[] arr) {
        boolean answer = true;
        int standard = 0; 
        int sum = 0 ;
        
        for(int j=1; j<=arr.length; j++){
            standard = standard + j;
        }
        
    
        for(int i=0; i<arr.length; i++){
            if(arr[i]>arr.length){
                answer = false;
            }
            sum = sum + arr[i];
            if(sum!=standard){
                answer = false;
            }
            else{
                answer = true;
            }
            
        }
        return answer;
    }
}

일단 1-n까지의 숫자가 있어야하기 때문에 n보다 큰 숫자가 존재하면 false를 return 하도록 하였다. 

중복된 숫자들을 해왔던 대로 Set을 통해 처리하려하였는데, 너무 비효율적일 것 같아서 고민하다가 1-n까지의 합과 배열요소의 합이 다르면 false를 return 하도록 하였다. 

 

문제 해설을 보고 무릎을 탁 쳤다.

그냥 arr를 정렬한다음에 arr[i]의 값이 i+1과 같지 않다면 false를 return 해주면 되는건데... 

앞으로 조금 더 쉽게 갈 수 있는 방법을 많이 생각해봐야겠다