사냥꾼
풀이 시간: 2일
결과: 구현 중 변경, 41점, 100점
접근방법
최초 접근
사대 기준으로 반복문을 돌며, 수식을 이용한 범위안에 동물이 있으면, cnt++.
위 구현 방식은 크나큰 결점이 있었는데, 쓸데 없는 수식과 조건부가 상당히 많았고, 무엇보다 위 문제는 사대별로 사격할 수 있는 새의 개수를 구하는 것이 아닌, 잡을 수 있는 동물의 수를 구하는 것이였다.
코드 구현 과정중 크나큰 결점이 있다는 걸 인지하고 수정에 들어갔다.
41점 풀이
동물 리스트에서 최대 x좌표를 구한 다음, 그 수만큼 사격범위(shooting_range)라는 배열을 만들고, 각 사로의 사격범위를 산정 후 동물리스트(animals)를 순회하면서 각 x좌표의 사격 범위 내의 동물들이 있으면, 카운팅하는 방식으로 구현했다.
- 핵심코드
int max_x = 0;
for (auto [tmp_x, tmp_y] : animals)
{
max_x = max(max_x, tmp_x);
}
vector<int> shooting_range(max_x + c, 0);
for (int i = 0; i < max_x + 1; i++)
{
for (int j = 0; j < hunters.size(); j++)
{
int h_pos = abs(i - hunters[j]);
shooting_range[i] = max(shooting_range[i], c - h_pos);
}
}
// 동물들을 순회해서 사격범위에 있으면 cnt++;
for (auto [victim_x, victim_y] : animals)
{
if (victim_y <= shooting_range[victim_x])
{
cnt++;
}
}
이방법은 사수가 많지 않다는 가정하에 효울적인 시간복잡도를 가지겠지만, 두가지 문제점이 있었다.
- 사로에 들어간 사수가 많을 수록, 에 가까운 시간복잡도를 가짐.
- 모든 비어있는 사로 또한 배열로 만들어 관리해야 함으로 m 크기의 배열이 추가로 필요.
결국 메모리 초과로 인해, M ≤ 100, N ≤ 100 수준의 테스트만 통과.
100점 풀이
더 이상의 구현 방법이 생각이 나지 않아서 문제 알고리즘 분류를 보니 이분탐색 이다.
생각을 바꿔 동물 기준으로 반복문을 돌아 가장 가까운 사로를 이분탐색으로 찾는 거 같았다.
나 같은 경우 이분탐색을 아무리 봐도 체득되지가 않았다.
개념은 이해가 되는데, 코드로 구현 시 너무 어려워서 그냥 c++ 라이브러리 가져다 써서 함수 딸깍으로 이분탐색을 구현 하였다.
// 동물을 순회해서 사격범위에 있으면 cnt++;
// 이분탐색으로 사대 위치 nlogn으로 찾은 다음 |xi-aj| + bj 계산식 활용
for (auto [victim_x, victim_y] : animals)
{
auto candidate_shoot_pos = lower_bound(hunters.begin(), hunters.end(), victim_x);
bool shooting = false;
if (candidate_shoot_pos != hunters.end())
{
int distance = abs(*candidate_shoot_pos - victim_x) + victim_y;
if (distance <= c)
shooting = true;
}
if (candidate_shoot_pos != hunters.begin())
{
// int distance = abs((*candidate_shoot_pos) - victim_x) + victim_y;
auto left_shooter = prev(candidate_shoot_pos);
int distance = abs(*left_shooter - victim_x) + victim_y;
if (distance <= c)
shooting = true;
}
if (shooting)
cnt++;
}
- 이번 문제풀이에서 얻은 점:
- 이터레이터 구조에 대해서 체득
auto candidate_shoot_pos = 이터레이터함수() 이렇게 선언 시 auto 는 interator type의 리스트가 되는 것이다.
즉, interator 이기에 반복문에서 다음 주기 때에도 이터레이터 값은 마지막 주소값을 유지중이다.
그러므로, 그 상태에서 다음 값을 찾기 때문에, 이터레이터 대상은 항상 정렬되어 있는게 좋을 것 같다.
**이건 진짜 크게 알아간다.**- lower_bound(a.begin(),a.end(), target) 사용법 체득 (upper_bound() 도 있음)
바이너리 서치해주는 이터레이터 함수로, 딸깍! 으로 바이너리 서치가 가능하다.
시작, 끝 범위와 목표값을 정하고, 크거나 같은 값 중 가장 처음 나오는 값의 반복자를 반환해준다.
upper_bound()도 있는데 큰 값 중 처음 나오는 값을 반환.
- 찾는 값이 주어진 데이터들 보다 크다면
lower_bound는 end() 반복자를 반환
upper_bound 또한 end() 반복자를 반환
- 찾는 값이 주어진 데이터들 보다 작다면
lower_bound는 begin() 반복자를 반환
upper_bound 또한 begin() 반복자를 반환
일단함