20551 마스터 배지훈의 후계자

정렬 후 탐색하는데 걸리는 시간복잡도를 관리하는 문제

시간초과에 주의해서 풀어야한다

https://www.acmicpc.net/problem/20551

1. 문제

---

간단 설명

N개의 원소를 가지는 배열 A를

오름차순으로 정렬해서 배열 B를 만든다

이후 이 배열 B에서 M번 주어지는 원소 D가 있는지 확인한다

있으면 그 원소의 해당 인덱스를, 존재하지 않으면 -1을 리턴한다

2. 문제 분석

---

필요변수

배열 A의 원소의 개수를 저장할 int N (1 <= N <= 2 * 100,000)

질문의 개수를 저장할 int M (1 <= N <= 2 * 100,000)

배열 A의 원소를 저장할 벡터 A (-1,000,000,000 <= A_i <= 1,000,000,000)

현재 질문 원소 D (-1,000,000,000 <= D <= 1,000,000,000)

주의점

• 시간 복잡도를 계산해볼 것
  • 2중 for문으로 수행시 얼마나 걸리는가
  • 정렬시에는? 또, 탐색시에는?
• 중복되는 원소가 주어질수도 있다
  • 일반적인 이분 탐색으로는 중복원소를 처리하지 못함

알고리즘

1. N과 M을 입력받는다
2. N번 반복하여 A의 원소들 입력받는다 O(N)
3. A를 정렬하여 B를 만든다
4. M번 원소 D에 대한 검색을 반복한다
	4-1. 정수 D를 입력받아 이 원소가 배열 B에 있는지 확인한다 
    4-2. 존재한다면 가장 먼저 등장한 위치를 출력해야한다

1. 이분탐색으로 시도

이분탐색으로 해결하려 했으나,

중복 원소가 존재할 때 처음 등장한 위치를 찾지 못하는 문제 발생

1. 2중 for문으로 시도했으나 역시 시간초과 발생

2중 for문의 시간 복잡도 계산 M은 최대 2×10^5 배열 B의 최대 크기는 2×10^5 worst case는 2 * 10^5 * 2 * 10^5 = 4 * 10^10 = 40,000,000,000 으로 약 400억 10억에 1초라고 치면 40초로 시간 초과 발생

1. 결국 이분탐색을 수행해야하는데, 처음 나오는 원소의 자리를 이분 탐색으로 어떻게 찾는지가 관건

• 이진탐색의 응용 버전인 Lower Bound, Upper Bound 알고리즘을 이용하였음

나중에 별도로 학습하고 포스팅해야겠다

3. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N, M;
	scanf("%d %d", &N, & M);

	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		int tmp; scanf("%d", &tmp);
		a[i] = tmp;
	}

	sort(a.begin(), a.end());

	for (int i = 0; i < M; i++) {
		int D; scanf("%d", &D);
	
		int res = lower_bound(a.begin(), a.end(), D) - a.begin();

		if (res != N && a[res] == D) {
			// lower_bound는 근사치를 찾기 때문에 일치하는 값이 없더라도 근처까지 감
			// 값이 일치하는지 확인하는 과정 필요
			printf("%d\n", res);
		}
		else {
			printf("-1\n");
		}
	}

	return 0;
}

C++ STL을 사용했지만, 다음에 Lower bound와 Upper bound 학습 후에는 직접 구현으로 재도전해봐야겠다