mminky's

code

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int N = A.size();
    int sum = (N+1)*(N+2)/2;
    for(int i=0; i<N; i++){
        sum -= A[i];
    }
    return sum;
}

Result

규모가 큰 집단에서는 오답이 나왔다.

이유를 찾아봐야겠다.

해결 아이디어

: 1~ N+1 까지의 수 중 N개가 배열 A에 들어있다.

 즉, 하나의 수가 제외되어있고 그 수를 찾는 것이 문제이다.

그래서 1~N+1의 합에서 각 배열에 들어있는 수를 모두 빼면 남는 값이 제외된 수 일 것이라 생각했다.

1에서 n까지의 합은 n*(n+1)/2 이다.

따라서 (N+1)(N+2)/2 - A[i]를 return했다.

--------------------------------------------------------------------------------------------------------------------

20-02-27 int형에서 long long 형으로 수정

정확도에서 100%가 나오는데 큰 규모에서 안 되는 이유가 궁금했다.

그래서 찾아보니 자료형의 차이인 것 같아 long long 형으로 수정을 하고

return할 때만 int로 형변환을 해서 반환했다.

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    long long N = A.size();
    long long sum = (N+1)*(N+2)/2;
    for(long long i=0; i<N; i++){
        sum -= A[i];
    }
    return (int)sum;
}

결과

<요약>

* int : 4바이트 (32/64비트 상관 없이)

signed int(부호가 있는 정수) 기준으로 0 ~ 2,147,483,647(16진수로 7FFFFFFF) 기록 가능

* long long : 8바이트

signed long long 기준 0 ~ 9,223,372,036,854,775,807(16진수로 7FFFFFFFFFFFFFFF) 기록 가능

(long long으로도 불가능하면 BigInteger)

( https://www.acmicpc.net/board/view/15516 gallopsys님 답변 참고)

즉, large test에서만 에러가 난 이유가 int형으로는 표현이 불가능했기 때문이라고 생각해

long long 타입으로 바꿨다!