자바 자료구조#04. List 연습문제_순열검사

문제 설명

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

제한사항

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

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

---

나의 풀이

import java.util.Arrays;

class Solution {
    public boolean solution(int[] arr) {
        
        boolean answer = true;
        
        // 1. 배열 정렬
        Arrays.sort(arr);
        
        // 2. 값이 순차적으로 증가하는지 검증
        for (int i = 0; i < arr.length; i++) {
            
            if (arr[i] != i+1) {
                answer = false;
                break;
            }
        }
        
        return answer;
    }
}

---

강의 풀이

1) 시간복잡도 O(n2) --> 효율성 테스트 실패

class Solution {
    public boolean solution(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
        	
            int found = 0;
            
            for (int a : arr) {
            
              if (a == i) {
              	  found++;
              }
           }
           
           if (found != 1) return false;
        }
        
        // 시간복잡도는 이중 for문으로 인해 O(n2)
        
        return true;
    }
}

2) Arrays 메소드 사용 --> // O(nlogn)

import java.util.*;

class Solution {
    public boolean solution(int[] arr) {
    	
        // 1. 정답 배열을 생성
        int[] answer = new int[arr.length];
        for(int i = 0; i < arr.length; i++) answer[i] = i + 1; // O(n)
        
    	Arrays.sort(arr); // O(nlogn)
        
        // 2. 주어진 배열이 정답 배열과 일치하는지 확인
        return Arrays.equals(answer, arr);	// O(n)
        
        // 시간복잡도는 O(nlogn) 와 O(n) 중 max값인 O(nlogn)
    }
}

출처 : 프로그래머스 스쿨 "[JAVA] 어서와! 자료구조 알고리즘은 처음이지?"