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이 되는..
2023. 7. 13.
