3. 배열 - 인덱싱 테이블 이용하여 시간복잡도 줄이기

문제

주어진 길이 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

 

풀이

배열의 인덱스별로 값들을 카운트하여 시간복잡도를 줄일 수 있음.  O(N^2) -> O(N)

합이 100인 수가 있는지 찾는 문제

- 100칸의 배열을 만들고, 주어진 값들을 100에서 뺀 후, 해당 인덱스에 카운트, 만약 값이 1일 경우면 프로그램 종료됨.

- 이중 반복을 사용해서 모든 원소값들을 더해서 100이 되는지 살펴본다면 O(N^2)이 나오지만, 배열 공간을 인덱싱하여 활용하면 O(N)이 나옴.

 

코드

 

알게 된 점

배열을 테이블 방식으로 사용시에 시간복잡도를 줄일 수 있음.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/3.%20%EB%B0%B0%EC%97%B4/0x03%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9C%202.cpp