[바킹독의 실전 알고리즘 강의] 배열

배열 정리

 

2021.02.25 - [Computer Science/DataStructure] - Array (배열)

 

 

배열 문제

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

O(N)으로 풀어보기

0부터 100까지 담을 수 있는 배열을 선언하고 arr를 순회하면서 현재 idx와 더해 100을 만들 수 있는 수가 있는지 찾기

int func2(int arr[], int n) {
	int countArr[] = new int[101];
    for(int idx = 0; idx < n; idx++) {
    	if(countArr[100-arr[idx] == 1) return 1;
        countArr[arr[idx]] = 1;
    }
    return 0;
}

• BOJ 10808 알파벳 갯수
• BOJ 2577 숫자의 개수
• BOJ 1475 방 번호
• BOJ 3273 두 수의 합

---

References By

 

https://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4