문제 설명
접근 방법
해당 문제에서는 사대(총을 쏘는 장소)들의 위치와 동물들의 위치가 주어졌을 때 특정 사정거리 내에서 잡을 수 있는 동물의 수를 요구하고 있다.
그래프 탐색을 이용해볼까?
처음 내가 생각했었던 방법은 동물들의 위치를 그래프에 나타낸 후 사대별로 그래프 탐색을 통해 사정 거리 내에 있는 동물들을 소거해가는 방식을 생각했었다.
하지만 문제에서 주어지는 사정거리의 최대치는 10억이라는 값으로 boolean형 2차원 배열이라고 할지라도 배열의 행, 열에 대해 각각 10억 크기만큼 할당하는 순간 힙 영역의 메모리 한도를 넘어가버린다. 심지어 해당 문제에서는 메모리 제한이 32MB로 이 문제는 그래프를 통해 해결할 수 없다고 판단이 들었다.
순차 탐색은?
이번에는 메모리를 적게 쓰기 위해 사대의 위치를 기억해놨다가 이후 동물의 위치가 주어질 때마다 앞서 저장해놓은 사대의 위치별로 해당 동물이 사거리 내에 들어오는지 검증했다. 결과는 시간 초과...
문제에서의 시간 제한은 단 1초인 반면, 실행 결과 4초라는 시간이 소요되었다.. 다시 문제를 살펴보니, 사대의 수는 최대 10만개, 동물의 수 역시 최대 10만개일 수 있다는 것이다. 즉, 이 같은 방식으로 연산했다간 최악의 경우 100억번의 연산이 발생할 수 있다는 것이다.
이제 남은 건 이분탐색..
최악의 경우 연산 횟수가 억대가 넘어가는데, 무언가를 탐색해야하는 상황이 올때면 그제서야 비로소 이분탐색을 떠올리게 된다. 베스트는 문제의 조건을 보고 탐색에 대한 시간 복잡도를 보고 이분 탐색으로 접근해야겠다고 판단하는 거지만, 나의 경우 일단 순차 탐색으로 해보고나서 안되면 이분탐색으로 접근한 것이다. 😂
이에 앞서 저장해놓은 사대의 배열 정보를 오름차순으로 정렬해주었다. 이후 배열의 첫 번째 인덱스와 마지막 인덱스를 시작점과 끝점으로 정한 후 이분 탐색을 하면서 사대와 동물 사이의 거리를 측정했고 이 값이 사거리 내에 있으면 결과값을 더해주고, 그렇지 않다면 사대의 x 좌표 위치와 동물의 x 좌표 위치를 비교하면서 범위를 점점 좁혀나갔다.
전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int[] guns = new int[m];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
guns[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(guns);
int x, y, start, end, mid, distance, result = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
start = 0;
end = m - 1;
while (start <= end) {
mid = (start + end) / 2;
distance = measure(x, y, guns[mid]);
if (distance <= l) {
result++;
break;
}
if (guns[mid] < x) {
start = mid + 1;
} else if (guns[mid] > x) {
end = mid - 1;
} else {
break;
}
}
}
System.out.println(result);
}
private static int measure(int x, int y, int gun) {
return Math.abs(gun - x) + y;
}
}
참고자료
- https://www.codeup.kr/problem.php?id=4791&rid=0
'Algorithm > CodeUp' 카테고리의 다른 글
[코드업 - 1484] 2차원 배열 달팽이 채우기 4-1 - Java (0) | 2021.11.29 |
---|---|
[코드업 - 1430] 기억력 테스트2 - Java (0) | 2021.11.15 |