[백준] 1920번: 수 찾기 풀이 및 해설(C++)

 

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

1920번: 수 찾기

 

C++로 작성한 백준 문제 1920번 수 찾기에 대한 문제 풀이다.

실버 4 문제로 자료구조, 정렬, 이진탐색이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

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개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

 

---

문제 파악하기

1. 순서가 상관 없으니 정렬하면 편하게 계산할 수 있다.
2. 정렬하고 이분 탐색으로 찾아낸다.

 

---

 

코드 및 설명

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main()
{
    fastio;
    int numbers1,numbers2,x;
    cin>>numbers1;
    vector<int> arr;
    for(int i=0;i<numbers1;i++){
        cin>>x;
        arr.push_back(x);
    }
    sort(arr.begin(),arr.end());
    cin>>numbers2;
    for(int i=0;i<numbers2;i++){
        cin>>x;
        if(upper_bound(arr.begin(), arr.end(), x) - lower_bound(arr.begin(), arr.end(), x)>0){
            cout<<"1"<<'\n';
        }
        else{
            cout<<"0"<<'\n';
        }
    }

    return 0;
}

 

 

값을 입력 받고, upper_bound와 lower_bound를 이용해 문제를 풀었다.

c++에서 사용하는 문법으로, 오름차순 정렬이 된 상태에서 효과적으로 사용할 수 있다.

 

두 함수는 모두 이진탐색을 써서 탐색 시간이 O(n)으로 짧다.

 

upper_bound(시작위치, 끝위치, 찾으려는 값)은 찾으려는 값을 초과하는 값이 어디에 처음 등장하는지 알려준다.

lower_bound(시작위치, 끝위치, 찾으려는 값)은 찾으려는 값 이상의 값이 어디에 처음 등장하는지 알려준다. 

 

 

즉, 오름차순으로 정렬되었을때 그 값이 존재한다면 upper_bound는 lower_bound보다 더 큰 값을 무조건 말할 것이다! upper_bound는 초과이고, lower_bound는 이상이니까.

값을 처음부터 찾았을 때 존재한다면 lower_bound는 거기서 멈추고 upper_bound는 한 칸이라도 더 간다.

 

만약 그 값이 존재하지 않는다면 두 함수는 같은 값을 말할 것이다.

둘 다 그보다 작은 수에서 점프해서 바로 그보다 큰 초과의 수를 말한 것이니까. 둘은 똑같이 말한다.

 

그래서 upper_bound에서 lower_bound를 빼서 값이 양수이면 존재하고, 그렇지 않다면 존재하지 않는다는 걸 알 수 있다.

 

---

 

헤매었던 부분

처음에 find() 함수를 통해 처음부터 끝까지 비교하였으나 시간초과가 났다. upper_bound와 lower_bound 함수가 낯설어서 살짝 헤매었다. 결국 upper_bound와 lower_bound 함수를 사용할 때 시간이 적게 걸린다는 걸 알고 서로 뺄 때 그 값을 추적할 수 있다는 아이디어가 중요한 것 같다.

 

처음에 vector와 algorithm을 제대로 include 하지 않아 에러도 났었다. 이런것도 빼먹지 않게 주의하자

 

 

 

 

 

---

 

마무리

if(upper_bound() - lower_bound()>0)으로 해당 범위에 값이 있는지 없는지 찾아낼 수 있다.  

 

 

이 문제와 비슷한 문제다.

2024.01.14 - [algorithm/Binary Search] - [백준] 10815번: 숫자 카드 풀이 및 해설(C++)

[백준] 10815번: 숫자 카드 풀이 및 해설(C++)