1920번 수 찾기 (이진탐색, sort)

#문제링크 : https://www.acmicpc.net/problem/1920

<처음 생각한 알고리즘>

  A를 오름차순으로 정렬하고, M과 비교시작! 낮은 인덱스부터 비교하는데, 같은 값을 찾으면 해당 M의 요소에 1저장, 같은 값을 찾지 못하거나, A(max)<M요소거나, M요소<A요소일 경우 M요소에 0 저장하고 break. 완전탐색에서 예외처리하여 완전탐색보다는 적게 탐색하지만 결국 복잡도는 비슷하다. return 시간초과. 배열들 메모리초과 위험이 있어서 전역변수로 배열 선언하는 것이 낫다.

1. Code

 

<수정한 알고리즘>

A를 정렬 후, A배열 안에서 M요소의 값과 동일한 값을 이진탐색하는 방법을 생각했다. A배열에서 한번 이진탐색하는데 걸리는 복잡도는 lgn이므로 M요소 n개에 대하여 nlgn의 복잡도일 것이라 추측된다. 배열들을 전역으로 선언하고, 이진탐색 함수를 작성하였다.

※주의사항

1. 전역으로 선언된 배열 함수의 인자로 굳이 안넣어도 됨.

2. 벡터 배열에서 V.size()의 반환값이 int가 아니고 다른거라 사용할 때 주의하거나 따로 int size로 저장.

3. std::ios_base::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL); -> 입출력 객체 가속화코드

4. 배열에 다시 값을 저장하는 부분을 최대한 줄일 것.

5. endl -> "\n" : endl의 속도가 많이 느리다.

2. Code

<STL binary_search 사용>

c++에서 제공하는 STL binary_search를 사용하여 문제를 풀어보았다. 코드가 훨씬 간단해진다.

※주의사항

1. 배열의 범위 설정 유의하기. 여기선 1~N까지의 인덱스로 저장했기에 +1을 전부 해준다.

3. Code