[2018 국민대 알고리즘대회 예제 - 1]

문제

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

 

제한사항

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

입출력 예

arr=[4,1,3,2]       result=true
arr=[4,1,3]         result=false

 

소스코드 및 풀이

 

#include<iostream>
#include<vector>
using namespace std;
 
bool solution(vector<int>arr) {
    
    bool answer;
    int A[] = { 0, };
    //벡터 arr을 0과 1로 표현하여 정렬한 배열
 
    int n = arr.size();//벡터 arr의 크기
 
    for (int i = 0; i < n; i++) {
        int j = A[i];
        //A[0]=4인 경우에는 4번째 A 배열에 대입
 
        A[j] = A[j] + 1;
        //A는 0으로 초기화시켰으므로 1로 만들어줌.
    }
 
    for (int i = 0; i < n; i++) {
        if (A[i] == 0||A[i]>1) 
            return false;
        //처음부터 n까지 연속되지 않아 0으로 잔류하거나 중복되어 여러 번 더해진 경우에는 false를 출력
    }
 
    return answer;
}

위의 문제에서 가장 중요한 포인트는 2가지 이다.

1. n개의 숫자들이 빠지지 않고 정렬이 되었는가?

2. 중복이 되었는가?

 

이를 위해 벡터 arr과 추가적으로 배열 A를 만들고자 한다.

 

 

예를 들어 벡터 arr은 4132라고 하였다. 이제 우리는 벡터 arr이 n까지 숫자가 빠진게 없는지, 중복이 되지 않았는지를 판단해야 한다.

 

①arr[0]을 추출하여 이를 arr[0]번째 배열에 저장한다.

 

예시로 든 벡터에서 arr[0]은 4이다. 이제 이를 4번째 배열에 저장한다.

 

② 위의 방법처럼 arr[1]을 추출하여 arr[1]번째 배열에 저장한다.

 

 

③ 이런식으로 n번 반복하여 실행한다. 실행 결과 만약에 4가 2번 있었다면(중복이라면) 4번째에 1을 두번 더해주어 2가 있을 것이다. 또한 벡터에 빠진 숫자가 있었다면 0이 존재하였을 것이다. 하지만 예시로 제시한 벡터 arr은 4132로 숫자 4개가 다 있고, 중복도 되지 않으므로 다음과 같은 배열 A가 출력된다.

 

④ 1부터 n까지 숫자가 0인지 1인지를 파악하여 1이 하나로도 없으면 false, n개의 숫자가 모두 1이면 true를 출력하도록 한다.

 

 

의견 및 반성

처음에는 그냥 sort를 하여 일일히 비교를 하는 방법을 사용하려고 하였다. 맨 마지막 숫자와 배열의 크기를 비교하여 숫자가 같으면 중복되는 숫자가 없다는 의미이므로 벡터의 중복여부를 판단하는 것은 평탄하였으나 빠진 숫자가 있는지를 판별하는 것은 쉽지만은 않은 것 같았다.

 

숫자가 존재할 때마다 0에서 하나씩 더하는 방법은 숫자가 1인지 아닌지를 판별하기만 하면 되므로 간단한 것 같았다. 앞으로 이런 방법을 애용해야 겠다.