[BaekJoon 10816][⚪4] 숫자 카드 2
❓ 문제
🎯 난이도
Silver ⚪4
🧠 풀이
1. 내 풀이 (동적 배열)
- 알고리즘
Data Structure
- 설명
vector를 사용하는 풀이이다.
vector를 사용해서 미리 가능한 모든 공간을 할당해놓고, 입력값에 따른 해당 인덱스의 숫자를 ++해주는 방식이다. 이러한 숫자 갯수 구하기 문제에서 가장 흔히 사용할 수 있는 트릭이기도 하다.
vector의 임의 접근 속도가 O(1)이므로 전체 시간 복잡도는 O(N)이라고 볼 수 있다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
constexpr int LIMIT{ 10000000 };
int iN{};
cin >> iN;
// 미리 모든 공간 할당
vector<int> vecCard(2 * LIMIT + 1);
while(iN--)
{
int iInput{};
cin >> iInput;
// iInput + LIMIT으로 하면 음수까지 커버 가능
++vecCard[iInput + LIMIT];
}
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
cout << vecCard[iInput + LIMIT] << ' ';
}
return 0;
}
2. 추가 풀이 1 (정렬 + 이진 탐색)
- 알고리즘
Data Structure,Sorting,Binary Search
- 설명
정렬과 이진 탐색 을 사용하는 방식이다.
입력값들을 저장하고, 이 중에서 특정 입력값이 몇 번 저장되었는가를 물어보는 문제이므로, 정렬과 이진 탐색이 딱 맞는 문제이다. 동시에 이 문제가 의도하는 방식의 풀이이기도 하다.
이진 탐색 중에 lower_bound와 upper_bound를 사용하기만 하면 된다.
lower_bound: 찾으려는 숫자가 시작되는 인덱스를 가르키는iterator반환upper_bound: 찾으려는 숫자를 초월하는 인덱스를 가르키는iterator반환
따라서 'upper_bound - lower_bound'로 찾으려는 숫자의 정확한 갯수를 찾을 수 있다. 또한 이진 탐색은 사전에 꼭 정렬을 해주어야 하는 것을 잊지 말자.
sort의 시간 복잡도는 O(N log N), lower_bound와 upper_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> vecCard{};
vecCard.reserve(iN);
while(iN--)
{
int iInput{};
cin >> iInput;
vecCard.push_back(iInput);
}
// 이진 탐색이기 때문에 미리 정렬
sort(vecCard.begin(), vecCard.end());
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
// (upper_bound - lower_bound)로 갯수 찾기
cout << upper_bound(vecCard.begin(), vecCard.end(), iInput) -
lower_bound(vecCard.begin(), vecCard.end(), iInput) << ' ';
}
return 0;
}
3. 추가 풀이 2 (해시 맵)
- 알고리즘
Data Structure,Set & Map,Hashing
- 설명
unordered_map을 이용하는 풀이이다.
단순하게 들어오는 입력값들을 unordered_map에 저장함과 동시에 value를 1씩 더해주는 방식이다.
주의할 점은 unordered_map은 '해시 테이블' 기반이므로, '해시 충돌'이 일어나거나 '리해싱'이 발생하지 않도록 경우에 따라서 넉넉한 공간 할당과 'load factor'의 조절을 해주는 것이 좋다.
unordered_map의 삽입, 삭제, 탐색의 비용은 O(1)이므로 전체적인 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
unordered_map<int, int> umapCard{};
umapCard.max_load_factor(0.7f); // 해시 충돌 피하기 위해 0.7f 정도면 충분
umapCard.reserve(iN * 2); // 재할당 방지 및 load_factor를 생각해서 넉넉하게 할당
while(iN--)
{
int iInput{};
cin >> iInput;
++umapCard[iInput];
}
int iM{};
cin >> iM;
while(iM--)
{
int iInput{};
cin >> iInput;
auto iter = umapCard.find(iInput);
cout << (iter == umapCard.end() ? 0 : iter->second) << '\n';
}
return 0;
}
💭 후기
세 풀이를 정리해 보았는데, 각각의 성능이 모두 다르다.
- 첫 번째 풀이 :
232ms,80148KB - 두 번째 풀이 :
292ms,3980KB - 세 번째 풀이 :
312ms,25988KB
이렇듯, 속도는 첫 번째 풀이가 가장 빠르지만 메모리는 가장 많이 잡아먹고, 두 번째 풀이가 가장 메모리가 적고, 세 번째 풀이는 가장 느리면서 메모리도 두 번째 풀이보다 훨씬 크다.
따라서 가장 보편적으로 좋은건 두 번째의 정렬 + 이진 탐색 풀이라고 보는 게 맞다. unordered_map은 아무리 reserve로 미리 할당하고 load factor 조절로 해시 충돌을 줄여도, 기본 '해싱' 과정과 노드 기반 메모리 구조의 낮은 '캐시 친화성' 때문에 속도도 늘어나고 '버킷'의 크기와 마찬가지로 노드 기반이기 때문에 메모리도 많이 차지 한다는 걸 알 수 있다.
Comments