백준 10807번 : 배열을 이용해 시간복잡도 줄이기

문제

총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오.

 

예제 입력

11
1 4 1 2 4 2 4 2 3 4 4
2

예제 출력

3

 

우선 배열에 N개의 정수를 다 저장하고, 배열을 순서대로 탐색하며 정수 v를 찾는 방법을 생각할 수 있을 것이다. 그렇게 하면 (입력을 제외하고) O(n)의 시간 복잡도를 가진다.

 

코드 예시

// 입력
int n, v;
int num[101];
cin >> n;
for (int i = 0; i < n; i++)
	cin >> num[i];
cin >> v;

// 본문
int count = 0;
for (int i = 0; i < n; i++)
    if (num[i] == v)
        count++;

// 출력
cout << count;

 

 

그러나 탐색 시간을 O(1)로 줄이는 방법이 있다. 바로 빈도 배열(freq)을 이용하는 것.

'빈도 배열'은 내가 자체적으로 만든 용어인데(..) 일반적으로 생각하는 데이터가 들어간 배열이 아닌,

데이터 내용을 인덱스로 설정하고, 그 인덱스 값이 입력으로 몇 번 들어왔는지 기록하는 배열이라고 할 수 있겠다.

 

이렇게 배열을 만들면, 원하는 데이터 내용이 몇 번 등장했는지 알기 위해서

freq[데이터 내용]만 하면 되므로, O(1) 만에 원하는 값에 접근할 수 있게 된다.

 

예시를 들면 다음과 같다.

이 문제의 경우 일반 배열에 값을 넣을 경우 아래와 같이 되겠지만,

0	1	2	3	4	5	6	7	8	9	10
1	4	1	2	4	2	4	2	3	4	4

빈도 배열에 값을 넣을 경우 다음과 같이 된다.

0	1	2	3	4	5	...
0	1	3	1	5	0

물론 이 문제의 경우 v의 범위가 -100 ~ 100 이므로 bias 값을 두어야 할 것이다. (배열의 인덱스는 음이 아닌 정수이므로)

bias = 100이라 하면, 다음과 같이 될 것이다.

0	1	2	...	100	101	102	103	104	...
				0	1	3	1	5

 

이 경우 시간 복잡도는 O(1)이 되지만, 보통은 입력받는 데이터의 개수(N)의 범위보다 입력받는 데이터의 크기 범위가 절대적으로 크므로 공간 복잡도가 늘어나게 된다. 즉, 시간 복잡도를 위해 공간 복잡도를 희생하는 전략인 것이다.

 

 

빈도 배열을 사용한 코드 예시는 다음과 같다.

코드 예시

// 입력
int n, v;
int num[202] = { 0, };
cin >> n;
int idx;
for (int i = 0; i < n; i++) {
    cin >> idx;
    num[idx + 100]++;
}
cin >> v;

// 본문 & 출력
cout << num[v + 100];

빈도 배열을 사용할 때는, 반드시 모든 값을 0으로 초기화시켜주자.

(전역 변수로 선언하거나, 예시와 같은 구문을 넣어 주면 된다.)