[백준,C++] 1920 : 수 찾기

728x90

문제

 

---

정수 N개가 주어진 배열 A[1], A[2], ..., A[N]이 있을 때, 해당 배열 안에 특정 정수 X가 존재하는지를 판별하는 프로그램을 작성하십시오.

입력

---

첫째 줄에는 자연수 N(1 ≤ N ≤ 100,000)이 주어지며, 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어집니다. 그 다음 줄에는 자연수 M(1 ≤ M ≤ 100,000)이 주어지고, 그 다음 줄에는 M개의 수들이 주어집니다. 이때, 주어진 M개의 수들 중에서 각각이 배열 A 안에 존재하는지를 판별하는 프로그램을 작성하면 됩니다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작습니다.

반응형

출력

 

---

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."

​

처음에 떠오른 생각은 첫 배열을 정렬하여 이진 탐색을 사용해 찾으면 좋겠다는 것이었다. 

이 아이디어를 구현하기 위해 열심히 이진 탐색 함수를 작성하던 중, C++의 `<algorithm>` 라이브러리에 이미 이진 탐색을 수행하는 STL 함수인 `binary_search`가 있다는 것을 발견했다.

binary_search(array.front(),array.end(), target);

형식으로 활용하면되고

이 함수를 사용해 문제를 풀면

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>

using namespace std;



int main() {
    int N;
 
    cin >> N;
   
    int i;
    int temp;
    vector<int> numbers;
    vector<int> tosearch;
    for (i = 0;i < N;i++) {
        cin >> temp;
        numbers.push_back(temp);
    }
    sort(numbers.begin(), numbers.end());
    int M;
    cin >> M;
    for (i = 0;i < M;i++) {
        cin >> temp;
        tosearch.push_back(temp);
    }
    int front;
    int end;
    int mid;
    for (int searching : tosearch) {
        if (binary_search(numbers.begin(), numbers.end(), searching)) {
            cout << 1 << '\n';
        }
        else {
            cout << 0 << '\n';
        }
    }
}

이렇게 다소 짧게 풀린다

​

그러나 알고리즘이나 자료구조를 공부하는 상황이라면 이진 탐색 함수를 직접 짤 수 있어야한다

bool binarySearch(const std::vector<int>& sortedVector, int target) {
    int left = 0;
    int right = sortedVector.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (sortedVector[mid] == target) {
            return true;  // Element found
        } else if (sortedVector[mid] < target) {
            left = mid + 1;  // Search in the right half
        } else {
            right = mid - 1;  // Search in the left half
        }
    }

    return false;  // Element not found
}

위 함수는 Target 값이 배열 (vector) 내에 있는지 없는지를 return하는 함수이다

​

<백준, C++, 1181: 단어정렬>

https://tonnykang.tistory.com/90

[백준,C++] 1181: 단어 정렬