길이범위에 따른 숫자 중복없는 배열

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

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

1. 범위를 벗어나는 값이 있는지 확인해보기

2. 범위를 벗어나지 않는 값이 몇번 등장하는지 체크하기

 

배열 체크 사용

-> 각 배열 안의 값이 배열 길이의 수만큼 있는지 체크

 

int chk[100001] = {0};
bool soltion(vector<int> arr)
{
    int n = arr.size(); //배열의 길이저장
    for(int i = 0; i  <  n; ++i)   //배열의 각 원소 모두 순회
        if(arr[i] < 1 || arr[i] > n)    
            return false;
    
        chk[arr[i]]++;  //각 배열의 원소가 몇번씩 나타났는지 확인,  
    
}
//for문을 빠져나왔다면 주어진 배열에는 범위를 벗어난 값이 없었던것이므로
// 중복된 값이 없는지 체크
for(int i = 1; i <= n; ++i)
     if(chk[i] != 1)
         return false;
    return true;
}

 

 

정렬사용

-> 정렬된 배열을 순서대로 순회하면서 1부터 n까지의 숫자가 모두 있는지 확인

 

bool solution(vector<int> arr)
{
    sort(arr.begin(), arr.end());
    for(int i = 0; i < arr.size(); ++i)
        if(arr[i] != i + 1)
            return false;
    return true;
}