알고리즘(algorithm) - 순열 검사

문제 설명

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

나의 풀이 )

배열을 정렬한 뒤 차례대로 값을 비교.

코드 )

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

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;

}

또 다른 풀이 1 )
범위를 벗어나지 않는 값이 몇번 나오는지 체크.


코드)

#include <iostream>
#include <vector>

using namespace std;

int check[100001] = { 0 };
bool solution(vector<int> arr)
{
int n = arr.size();

for (int i = 0; i < n; ++i)
{
if (arr[i] < i || arr[i] > n)
return false;
check[arr[i]]++;
}

for(int i = 1; i <= n; ++i)
if(check[i] != i)
return false;

return true;
}

또 다른 풀이 2 )
배열안에 있는 값을 모두 더한 값을 1부터 배열크기까지의 정수를 더한값을 비교.


코드)

#include <vector>
#include <iostream>
using namespace std;

bool solution(vector<int> arr)
{
    bool answer = true;

    long a = 0;
    long b = 0;

    for( int i = 0 ; i < arr.size(); ++i )
    {
        a += ( i + 1 );
        b += arr[i];
    }

    if( a!= b )
        answer = false;


    return answer;
}

문제 출처 : https://programmers.co.kr/learn/courses/18/lessons/1877 (프로그래머스 예제)