백준 11663 선분 위의 점
문제: 백준 11663번 선분위의점
문제
일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.
출력
‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.
| 예제 입력 | 예제 출력 |
|---|---|
|
5 5 1 3 10 20 30 1 10 20 60 3 30 2 15 4 8 |
3 2 4 2 0 |
풀이
1차 시도
아주 단순히 생각하여 점의 개수 만큼 Array를 생성한 후 좌표를 기록하고,
반복문을 한번 더 돌리면서
for (int j = 0; j < N; j++)
if (dot[j] >= min && dot[j] <= max) count++;를 시도했다. 그리고 개같이 시간 초과. 날로 먹을 생각은 하지 말라길래 돌아가기로 했다.
import java.util.*;
import java.io.*;
class Main {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] dot = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) dot[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; i++) {
int count = 0;
st = new StringTokenizer(br.readLine());
int min = Integer.parseInt(st.nextToken());
int max = Integer.parseInt(st.nextToken());
for (int j = 0; j < N; j++)
if (dot[j] >= min && dot[j] <= max) count++;
sb.append(count).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
}
2차 시도
시간 초과가 일어나는 이유가 2중 반복문에서 발생한다고 판단하여 누적합으로 방향을 바꿨다.
사실 누적합도 날로 먹을 생각이긴 하다.
int[] dotPfx = new int[1000000001];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) dotPfx[Integer.parseInt(st.nextToken())]++;
for (int i = 1; i <= 1000000001; i++) dotPfx[i] += dotPfx[i - 1];
~~~
sb.append(dotPfx[max] - dotPfx[min - 1]).append("\n");
입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.
문제에서 주어진 좌표의 개수만큼 Array를 생성하고 반복문을 돌며 좌표마다
0에서부터 현재 좌표까지 존재하는 점의 개수로 만들어준다.
양이 좀 많긴 하지만 O(N)의 시간을 가지는 만큼 시간 초과를 피할 수 있다.
메모리 초과
시간복잡도와 공간복잡도를 둘 다 어겼다.
법이 없어야 살 수 있는 사람이다.
import java.util.*;
import java.io.*;
class Main {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] dotPfx = new int[1000000001];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) dotPfx[Integer.parseInt(st.nextToken())]++;
for (int i = 1; i <= 1000000001; i++) dotPfx[i] += dotPfx[i - 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int min = Integer.parseInt(st.nextToken());
int max = Integer.parseInt(st.nextToken());
sb.append(dotPfx[max] - dotPfx[min - 1]).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
}
3차 시도
시간과 공간에서 성가신 제약이 있는걸 확인했기에
O(N²)보단 빠른 이분탐색O(NlogN)으로 풀어본다.
이를 위해 1차 시도로 돌아와 추가로 이분 탐색 메서드를 생성한다.
static int[] dot;
~~~
dot = new int[N];
~~~
sb.append(binary(max + 1) - binary(min)).append("\n");
~~~
static int binary(int dot) {
int low = 0, high = dots.length;
while (low < high) {
int mid = (low + high) / 2;
if (dots[mid] >= dot) high = mid;
else low = mid + 1;
}
return low;
}
이분 탐색을 통해 선분 내에 좌표 개수를 계산하여
최대 - 최소 로 값을 구했다.
import java.util.*;
import java.io.*;
class Main {
static int[] dots;
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
dots = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) dots[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; i++) {
int count = 0;
st = new StringTokenizer(br.readLine());
int min = Integer.parseInt(st.nextToken());
int max = Integer.parseInt(st.nextToken());
sb.append(binary(max + 1) - binary(min)).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
static int binary(int dot) {
int low = 0, high = dots.length;
while (low < high) {
int mid = (low + high) / 2;
if (dots[mid] >= dot) high = mid;
else low = mid + 1;
}
return low;
}
}
틀렸다...
맞는데 왜 틀렸다는건지
이번엔 틀릴리가 없는데 문제가 어디서 발생하는지 이해가 안되어GPT에게 손을 빌렸다.
Arrays.sort(dot);
입력 단계에서
| 예제 입력 | 예제 출력 |
|---|---|
|
5 5 1 3 10 20 30 (여기) 1 10 20 60 3 30 2 15 4 8 |
3 2 4 2 0 |
깔끔하게 오름차순으로 제공해주길래 그냥 오름차순으로 주나보다 했더니
치사하게 이런 곳에서 블러핑을 쳤나보다.
문제를 다시 읽어보니 좌표를 작은 수에서 큰 수로 준다는 조건이 없긴 했다.
제출
import java.util.*;
import java.io.*;
class Main {
static int[] dots;
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
dots = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) dots[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; i++) {
int count = 0;
st = new StringTokenizer(br.readLine());
int min = Integer.parseInt(st.nextToken());
int max = Integer.parseInt(st.nextToken());
sb.append(binary(max + 1) - binary(min)).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
static int binary(int dot) {
int low = 0, high = dots.length;
while (low < high) {
int mid = (low + high) / 2;
if (dots[mid] >= dot) high = mid;
else low = mid + 1;
}
return low;
}
}
후기
굳이 날로 먹을 시도를 하지 않았으면 훨씬 빨리 풀었을텐데
