[배열] 두 수의 합이 100인 경우

[실전 알고리즘] 0x03강 - 배열

 

해당 블로그 내의 강의를 자바 언어로 풀면서 학습한 내용을 정리하고 있습니다.

 

int[] numbers = {1, 23, 53, 77, 60};

 

우선 0 ~ 100까지의 숫자를 랜덤으로 가진 배열이 주어진다.

 

주어진 배열에서 두 수를 더해 합이 100이 되는 경우가

존재하면 1, 존재하지 않으면 2를 출력하는 문제로

 

가장 단순하게 생각하면 배열의 특정 요소와 나머지 요소를 모두

번갈아가며 비교하여 100이 되는 경우가 있는지 확인하는 방법이 있다.

 

단순하지만 시간복잡도가 효율적인 방법은 아니기 때문에

더 좋은 방법은 새로운 배열을 만들어 기록하는 방법이다.

 

int[] save = new int[101];

 

위와 같이 0 ~ 100까지의 숫자가 출현했는지 여부를 기록할

배열을 0으로 초기화 시켜두고

숫자가 등장하면 해당 값의 등장 여부를 1로 기록한다.

 

for (int number : numbers) {

    if (save[100 - number] == 1 || number == 100) {
        System.out.println(1);
        return;
    }
    save[number] = 1;
}

System.out.println(0);

 

현재 숫자와 더해 100이 될 수 있는 값이 이전에 등장했거나 현재 숫자가 100이라면

합이 100인 경우가 존재하는 것을 알 수 있기 때문에

1을 출력하고 존재하지 않는다면 0을 출력하면 된다.

 

중복된 계산을 해야하는 경우에는 배열 같은 자료구조를 이용해

계산 결과를 저장하여 중복된 계산을 피하는 방식이 효율적이다.