[BaekJoon 1920][⚪4] 수 찾기
❓ 문제
🎯 난이도
Silver ⚪4
🧠 풀이
1. 내 풀이 (해시 셋)
- 알고리즘
Data Structure,Set & Map,Hashing
- 설명
unordered_set 컨테이너를 사용한 풀이이다.
값의 중복이 허용되지 않으므로 unordered_set에 입력값을 넣고 count로 해당 값이 존재하는지 찾아내는 방식이다.
find를 쓸 수도 있지만, find는 반환값이 해당 값의 iterator를 반환하므로 해당 값을 직접 사용하고 싶을 때 사용하는 것이 좋다. 그에 반해 'count'는 해당 값의 갯수를 반환하고 'unordered_set'은 값의 중복이 없으므로 '1'을 반환하면 존재하는 것으로 쉽게 판단 가능하다.
unordered_set의 삽입/삭제/탐색 시간은 O(1)이므로 전체 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
unordered_set<int> setNumber{};
setNumber.reserve(iN);
while(iN--)
{
int iInput{};
cin >> iInput;
setNumber.insert(iInput);
}
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
// unordered_set은 중복 허용하지 않으므로 count의 결과가 0, 1로만 나옴
cout << setNumber.count(iInput) << '\n';
}
return 0;
}
2. 추가 풀이 1 (정렬 + binary_search)
- 알고리즘
Sorting,Binary Search
- 설명
binary_search 함수를 사용하는 풀이이다.
이분 탐색의 응용이 필요한 경우는 직접 알고리즘을 구현해야 하지만, 찾으려는 값이 존재하는지만 알아내는 경우는 'binary_search' 함수를 사용하면 된다. 존재 여부를 bool값으로 반환하므로 바로 써먹기가 아주 좋다.
주의할 점은 binary_search 함수 또한 내부 작동 원리는 이분 탐색이므로 사용 전에 꼭 값들의 정렬이 필요하다.
sort의 시간 복잡도는 O(N log N)이고 이분 탐색의 시간 복잡도는 O(log N)를 N번 반복하므로 전체 시간 복잡도는 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<int> vecNumber(iN);
for(int i = 0; i < iN; ++i)
{
cin >> vecNumber[i];
}
// 이분 탐색을 위해선 정렬이 되어있어야 한다
sort(vecNumber.begin(), vecNumber.end());
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
// 찾으면 1, 없으면 0 출력
cout << (binary_search(vecNumber.begin(), vecNumber.end(), iInput) ? 1 : 0) << '\n';
}
return 0;
}
3. 추가 풀이 2 (정렬 + lower_bound)
- 알고리즘
Sorting,Binary Search
- 설명
lower_bound 함수를 사용하는 방법이다.
이분 탐색과 관련한 함수는 binary_search 외에도 lower_bound, upper_bound가 존재하는데 이 중에 lower_bound 함수를 사용하는 방식이다.
lower_bound는 찾으려는 값의 시작 위치를 가르키는 'iterator'를 반환하므로, 이를 이용하면 된다.
위와 마찬가지로 lower_bound도 내부 구조는 이분 탐색으로 시간 복잡도가 O(log N)이므로, 전체 시간 복잡도는 O(N log N)이다
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<int> vecNumber(iN);
for(int i = 0; i < iN; ++i)
{
cin >> vecNumber[i];
}
// 이분 탐색을 위해선 정렬이 되어있어야 한다
sort(vecNumber.begin(), vecNumber.end());
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
// lower_bound로 iInput이 시작되는 지점을 찾음
auto iter = lower_bound(vecNumber.begin(), vecNumber.end(), iInput);
// lower_bound로 찾은 iterator가 end가 아니고 내부값이 iInput이면 true
cout << (iter != vecNumber.end() && *iter == iInput ? 1 : 0) << '\n';
}
return 0;
}
💭 후기
전형적인 이분 탐색 문제인데, 시간을 더 줄일 수 있을까 싶어서 다른 방법을 시도해봤다. 분명히 이분 탐색을 사용하는 풀이들은 시간 복잡도가 O(N log N)이고, 내 풀이는 O(N)인데, 실제 걸리는 시간은 다음과 같다.
- 첫 번째 풀이 :
56ms - 두 번째 풀이 :
48ms - 세 번째 풀이 :
48ms
이는 이분 탐색은 내부적으로 정수끼리의 연산이 주가 되고 O(log N)의 값이 매우 작은데 비해, unordered_set은 해싱, 노드 포인터의 낮은 캐시 친화성 등의 오버헤드에 의해 상수 시간이 크기 때문이다.
따라서 특정 범위 내에서의 값을 찾는다면 이분 탐색이 최적화된 방식이라는 것을 알 수 있다.
Comments