'Algorithm'에 해당되는 글 23건

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].
  
  

알고리즘을 생각했을때, 가장 중요했던 점은 범위내에서 1 ~ N 이 배열 A에 단 하나씩 존재해야 참이라는 점이었습니다.

즉, 중복이 있을 경우에는 Permutation이 아니라는 뜻이고 원소를 중복 저장하지 않는 Set 의 성질을 이용해서 알고리즘을 짰습니다. 

먼저, 1 부터 N 까지 모든 수를 가진 Set 을 만든 후  배열 A 의 모든 원소에 대해 모두 remove 해보고 그 결과 Set 에 원소가 없으면 한번씩만 존재한 Permutation 이란 뜻이고 원소가 남아있으면 아니란 개념을 이용했습니다.

HashSet 에서 Set 에 없는 원소를 remove 할 경우 false 를 반환하고 아무 작업도 일어나지 않기 때문에 문제가 없습니다.

import java.util.*;

class Solution {
    public int solution(int[] A) {
        
        HashSet<Integer> set = new HashSet<>();
        
        for(int i = 1; i <= A.length; i++){
            set.add(i);
        }
        
        for(int j = 0; j < A.length; j++){
            set.remove(A[j]);
        }
        
        if(set.size() == 0){
            return 1;
        }
        else{
            return 0;
        }
    }
}