import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Meeting implements Comparable<Meeting> {
int start, end, people;
Meeting(int start, int end, int people) {
this.start = start;
this.end = end;
this.people = people;
}
@Override
public int compareTo(Meeting o) {
return this.end - o.end; // 종료 시간 기준 정렬
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
Meeting[] meetings = new Meeting[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int people = Integer.parseInt(st.nextToken());
meetings[i] = new Meeting(start, end, people);
}
// 종료 시간 기준 정렬
Arrays.sort(meetings);
// DP 배열 및 종료 시간 배열
int[] dp = new int[n];
int[] endTimes = new int[n];
for (int i = 0; i < n; i++) {
endTimes[i] = meetings[i].end; // 종료 시간만 저장
}
dp[0] = meetings[0].people; // 첫 회의 인원 초기화
for (int i = 1; i < n; i++) {
// 현재 회의 인원
dp[i] = meetings[i].people;
// 이전 회의 중 겹치지 않는 가장 마지막 회의 찾기 (이분 탐색)
int idx = binarySearch(endTimes, meetings[i].start);
if (idx != -1) {
dp[i] += dp[idx];
}
// 이전 최대값과 비교
dp[i] = Math.max(dp[i], dp[i - 1]);
}
System.out.println(dp[n - 1]);
}
// 이분 탐색: 종료 시간이 target 이하인 가장 마지막 인덱스를 찾음
private static int binarySearch(int[] endTimes, int target) {
int left = 0, right = endTimes.length - 1;
int result = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (endTimes[mid] <= target) {
result = mid; // 가능한 인덱스 갱신
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}
메서드 영역은 프로그램을 실행하는데 필요한 공통 데이터를 관리한다. 이 영역은 프로그램의 모든 영역에서 공유한다.
클래스 정보: 클래스의 실행코드(바이트 코드), 필드, 메서드와 생성자 코드 등 모든 실행 코드가 존재한다.
static 영역: static 변수들을 보관한다.
런타임 상수 풀: 프로그램을 실행하는데 필요한 공통 리터럴 상수를 보관한다.
스택 영역
스택 영역은 자바 실행 시 생성이 되는데, 스레드 1개당 하나의 스택이 생성된다. 그리고 메소드가 호출될 때마다 스택 영역에는 스택 프레임이 하나씩 쌓이게 된다.
스택 프레임: 지역 변수(매개변수 포함), 중간 연산 결과, 메소드 호출 정보 등을 포함한다. - Local Variables: 메소드의 지역 변수들을 갖는다. - Operand Stack: 메소드 내 계산을 위한 작업 공간이다. - Constant Pool Reference: 런타임 상수 풀의 참조를 갖는다.
힙 영역
힙 영역은 인스턴스와 배열이 생성되는 곳이다. 가비지 컬렉션(GC)이 주로 이루어지며 더 이상 참조되지 않는 객체는 GC에 의해 청소된다. 쓱싹.
👶 인스턴스는 내부에 변수와 메서드를 가지고 있는데, 그럼 각각의 인스턴스의 메서드는 인스턴스가 생성될 때마다 인스턴스 영역에 들어가게 되는지,,? 👩🏻💻 인스턴스들의 필드 값은 모두 다른 주소를 가져야겠지만, 메소드의 코드는 모두 동일합니다. 따라서 메서드는 메서드 영역에서 공통으로 관리됩니다. 즉,인스턴스의 메서드를 호출하면 힙영역이 아닌 메서드 영역에 있는 코드가 호출이 됩니다.
2. Static 변수 (정적 변수)
static 키워드가 붙는 변수는 모두 메서드 영역(스태틱 영역)에서 관리가 된다. 즉, 인스턴스 영역에 생성되지 않는 것이다.
위와 같이 인스턴스와 함께 생성이 되지 않기 때문에 현재까지 인스턴스를 몇 개를 만들었는지 확인하는static int count변수가 사용 가능하다. 즉,스태틱 변수는 클래스 하나당 하나만 생성이 되며 인스턴스 변수는 인스턴스의 수만큼 생성이 된다.
변수와 생명주기
지역 변수(매개변수 포함):스택 영역의 스택 프레임에 저장되며 메서드가 종료되면 프레임이 제거됨과 동시에 제거된다.
인스턴스 변수:힙 영역에 저장되며 인스턴스가 개발자에 의해 제거되거나 GC가 발생하기 전까지 생존한다.
클래스 변수(스태틱 변수, 정적 변수):메서드 영역의 static 영역에 저장되며 JVM 로딩과 함께 생성되며 JVM이 종료되면 함께 생명이 끝난다.
Static 변수 접근법
1. 인스턴스를 통해 접근
Data data = new Data();
data.count++;
2. 클래스를 통한 접근
Data.count++;
스태틱 변수는 클래스 변수라고 불리는 만큼 클래스를 통해 접근하는 것이 가독성이 훨씬 좋다. 인스턴스 변수에 접근하는 것처럼 보이는 것 보다 한눈에 명확히 클래스 변수에 접근하는 것처럼 보이는 것이 더욱 명확하기 때문이다.
3. Static 메서드 (정적 메서드)
Static 메서드는 정적 변수와 마찬가지로 스태틱 영역에서 관리된다. 따라서 마찬가지로인스턴스 생성 없이 클래스 명을 통해 호출이 가능하다.
public class Math() {
public static int add(int a, int b) {
return a+b;
}
public static int subtract(int a, int b) {
return a-b;
}
}
위와 같은 유틸리티 클래스(Utility Class, 정적 메서드만 존재하는 클래스)에서 이러한 접근법은 유용하게 쓰인다.
정적 메서드 접근법
1. 인스턴스를 통해 접근
Math math = new Math();
math.sum(1, 2);
2. 클래스명을 통해 접근
Math.sum(1, 2);
3. static import를 통해 접근 (정적 변수도 import 가능)
import static 패키지명.Math.*;
sum(1, 2);
정적 메서드 사용 시 주의할 점
static 메서드는 static 만 사용 할 수 있다.
생각해보면 당연하다. 정적 메서드는 참조값이 없다. 그런데 인스턴스 변수나 메서드를 사용하려면 참조값을 알아야한다. 따라서정적 메서드에서 인스턴스 변수나 메서드를 불러오면 자바는 어느 주소를 찾아가야 하는지 알 수 없게 되고(참조값 부재), 컴파일 에러가 뜨게 된다.
4. main() 메서드
인스턴스 생성 없이 사용하는 메서드의 가장 대표적인 예는 main() 메서드이다. 따라서main에서 호출할 메서드 또한 모두 static 이어야 한다. 변수 또한 마찬가지다.
정적 변수를 작성해서 에러가 나는 경우
public class Math() {
public int count;
public static void main(String[] args) {
count++;
}
}
정적 메서드를 사용해서 에러가 나는 경우
public class Math() {
public static void main(String[] args) {
test();
}
public void test() {
System.out.println("test!");
}
}
각 플랫폼에서 맨해튼거리로 L 보다 같거나 작은 거리 내 동물들을 다 잡을 수 있다고 가정했을 때
잡을 수 있는 모든 동물의 수를 구하는 문제이다!
플랫폼의 수를 M, 동물의 수를 N, 거리를 L이라고 둔다.
플랫폼의 y좌표는 어짜피 0이므로, 플랫폼의 x좌표를 저장할 배열을 만들어준다. 값을 입력받고 오름차순 정렬해준다.
Long[] plate = new Long[M];
...
Arrays.sort(plate);
이렇게 된다면 plate[0] 에는 x축에 가장 가까운 사대가, plate[plate.length-1]에는 x축에서 가장 먼 사대가 되는 것이다.
동물의 x, y좌표를 입력받으면서
plate를 기준으로 start값과 end 값을 잡아준다.
가장 초기에는 start는 0, end는 plate.length-1로 둔다.
mid값은 (start + end)/2 이다.
이분탐색을 돌며 plate[mid]에서 해당 동물의 거리를 구하고, 그 값을 기준으로
1. L과 같거나 작으면 답을 추가한다.
2. L보다 크다면 ...
// 모든 사대는 y의 값이 0이다. 따라서 맨해튼 거리를 구할 때 mid값이 바뀌어도 x좌표끼리의 값만 바뀌지, y 값은 항상 일정하다.
2-1. plate[mid] - x가 0보다 크다면, L과 같거나 작게 만드려면 plate[mid] 의 값이 줄어들어야된다. 따라서 mid값을 줄이기 위해 end값을 mid - 1 로 바꾼다.
2-2. plate[mid] - x가 0보다 작다면, plate[mid] 값은 항상 양수기때문에 값이 커져야된다. 따라서 start값을 mid + 1로 바꾼다.
이렇게 이분탐색을 시행하면 문제가 풀린다!
이분탐색을 들어가기 전
동물의 y값이 L보다 이미 큰 상태라면 -> 모든 동물이 다 포함될 수 없으므로 이분탐색 하지말고 바로넘긴다!
이거까지 하면 실행속도가 더 줄어든다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int M = Integer.parseInt(st.nextToken()),
N = Integer.parseInt(st.nextToken()),
L = Integer.parseInt(st.nextToken());
Long[] plate = new Long[M];
st = new StringTokenizer(bf.readLine());
for(int i=0;i<M;i++) {
plate[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(plate);
int ans = 0;
for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
Long x = Long.parseLong(st.nextToken()), y = Long.parseLong(st.nextToken());
int start = 0, end = M-1;
if(y > L) continue;
while(start <= end) {
int mid = (start+end)/2;
Long target = plate[mid] - x;
Long distance = Math.abs(target) + y;
if(distance <= L) {
ans++;
break;
} else if(target > 0) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
System.out.println(ans);
}
}
