int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하는지 구하기

 

 

Q. 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1, 존재하지 않으면 0 반환하는 함수 func2(int arr[], int N) 작성 (arr의 각 수는 0 이상 100 이하, N은 1000 이하)

 

 

func2({1, 52, 48}, 3) = 1;

func2({50, 42}, 2) = 0;

func2({4, 13, 63, 87}, 4) = 1;

 

 

public static void main(String[] args) {

    int[] arr = {4, 13, 63, 87};
    int N = 4;

    System.out.println("answer: " + func2(arr, N));
}

private static int func2(int[] arr, int n) {

    // arr에서 0부터 길이-1까지 두개씩 뽑아서 합이 100인지 확인
    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;
}

출력

answer: 1

 

 

=> 시간 복잡도 O(N²) 

 

 

 

 

다른 방법) 

 

public static void main(String[] args) {

    int[] arr = {4, 13, 63, 87};
    int N = 4;

    System.out.println("answer: " + func2(arr, N));
}

private static int func2(int[] arr, int n) {

    // 값을 하나 선택해서 이전에 그 값과 합쳐 100이 나오는 수가 등장했으면 1, 등장한 적 없으면 0 
    int[] count = new int[101]; 	// 0 ~ 100 까지 담길 수 있는 101칸 배열

    // arr배열의 값을 돌면서 100-arr[i]인 수가 이전에 등장한 적 있으면 1, 없으면 0
    // 예) 100-4= 96, 등장한 적 없으니 0인데, 96 입장에서는 4가 등장했으니 4에 +1
    for(int i=0; i<n; i++) {
        if(count[100 - arr[i]] == 1) {
            return 1;
        }
        count[arr[i]] = 1;
    }
    return 0;
}

 

 

=> 시간복잡도 O(N)

 

N개의 원소를 도는 동안 합이 100인 쌍을 찾지 못했으면 0 반환, 

나와 합이 100이 되는 원소를 매 순간마다 O(1)에 찾고 이 행위를 N번 반복하기 때문