[배열 문제2]

문제

• 주어진 배열에서 두 숫자의 합이 100이 되는 경우가 있는지 확인

방법 1

• 완전 탐색
• 0부터 N까지 다 탐색해서 합이 100인게 있는지 다 검사를 해야한다.
• O(N^2)

int func2(int arr[], int N) {
    for(int i=0;i<N;i++) {
        for(int j=i+1;j<N;j++) {
            if(arr[i] + arr[j] == 100) {
                return 1;
            }
        }
    } return 0;
}

방법 2

• 미리 결과값을 저장할 0으로 초기화된 배열을 만든다.
• 함수 func2
  - occur 배열을 사용하여 숫자가 배열에 등장했는지 여부를 기록합니다.
  - 배열을 순회하며 각 숫자 arr[i]에 대해 100 - arr[i]가 이미 등장했는지 확인합니다.
  • 이미 등장했다면 두 숫자의 합이 100이므로 1을 반환합니다.
    - 현재 숫자를 occur 배열에 기록합니다.
• O(N)

#include <iostream>
#include <algorithm>

using namespace std;

int func2(int arr[], int N) {
    int occur[101] = {}; // 0으로 초기화된 101 크기의 배열

    for (int i = 0; i < N; i++) {
        if (occur[100 - arr[i]] == 1) { // arr[i]와 합해서 100이 되는 수가 존재하는지 확인
            return 1;
        }
        occur[arr[i]] = 1; // 현재 수를 기록
    }
    return 0; // 합해서 100이 되는 두 수가 없으면 0 반환
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cout << "Enter the number of elements in the array: ";
    cin >> N;

    int arr[N];
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int result = func2(arr, N);
    if (result == 1) {
        cout << "There are two numbers in the array that add up to 100." << endl;
    } else {
        cout << "There are no two numbers in the array that add up to 100." << endl;
    }

    return 0;
}