문제
“폐구간”이란 두 실수 a와 b를 포함하여 그 사이에 속한 모든 실수의 집합으로 [a,b]로 표기한다. 이 때 폐구간 [a,b]의 양 끝점인 a와 b는 항상 a≤b 의 관계를 만족한다. 두 개의 폐구간 [a,b] 와 [a′,b′]는 하나가 다른 하나를 완전히 포함하면 서로 “중첩”되어 있다고 말한다. 만약 어떤 폐구간들을 원소로 하는 집합이 있고, 그 집합에서 임의의 두 원소(폐구간)이 모두 중첩되어 있는 경우 “그 폐구간의 집합은 완전 중첩되어 있다”고 이야기한다. 예를 들어, { [ 1 , 10 ] , [ 2 , 5 ] , [ 3 , 4 ] , [ 4 , 4 ] } 의 폐구간의 집합은 완전 중첩되어 있다. 이 문제에서는 총 N개의 폐구간이 입력으로 주어질 때 완전 중첩된 부분집합 중 가장 원소의 개수가 많은 것을 찾고, 그 부분집합에 속한 폐구간의 개수를 출력하는 것을 목표로 한다.
예를 들어 입력으로 총 6개의 폐구간 [ 1 , 10 ] , [ 2 , 5 ] , [ 3 , 4 ] , [ 4 , 4 ] , [ 1 , 3 ] , [ 3 , 8 ]이 주어질 경우, 완전 중첩된 부분집합은 { [ 2 , 5 ] , [ 3 , 4 ] } , { [ 2 , 5 ] , [ 4 , 4 ] } , { [ 3 , 4 ] , [ 4 , 4 ] } , { [ 2 , 5 ] , [ 3 , 4 ] , [ 4 , 4 ] } , { [ 3 , 4 ] , [ 4 , 4 ] , [ 3 , 8 ] } … { [ 1 , 10 ] , [ 2 , 5 ] , [ 3 , 4 ] , [ 4 , 4 ] } 등이 있다. 이중 “원소 개수”가 가장 많은 것은 { [ 1 , 10 ] , [ 2 , 5 ] , [ 3 , 4 ] , [ 4 , 4 ] } 이며, 이 때 “원소 개수”는 ‘4’이다.
폐구간의 집합이 주어질 때 완전 중첩된 부분집합 중, “원소 개수”가 가장 많은 부분집합의 “원소 개수”를 구하는 프로그램을 작성하시오.
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T개의 테스트 케이스가 주어진다. ( 1≤T≤20 ) 각각의 테스트 케이스 첫 번째 줄에는 폐구간의 개수를 나타내는 정수 N(1≤N≤100,000)이 주어진다. 그 다음 이어지는 N 개의 각 줄에는 두 개의 정수 a와 b ( −10,000,000≤a≤b≤10,000,000 )가 주어지며, 이는 폐구간 [a,b]를 의미한다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다. 그 다음 줄에는 각 테스트 케이스로 주어지는 N 개의 폐구간 집합의 완전 중첩된 부분집합 중 “원소 개수”가 가장 많은 부분집합의 “원소 개수”를 정수형태로 출력한다. 완전 중첩 부분집합이 없을 경우에는 ‘1’을 출력한다.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Solution {
static int Answer;
static int min, max;
static void changeValue(int n, int left, int right) {
if(min < left) min = left;
if(max > right) max = right;
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 1~20
for(int test_case = 0; test_case < T; test_case++) {
Answer = 0;
int N = sc.nextInt(); // 1~100000
int[][] num = new int[N][2]; //-10000000 ~ 10000000
min=Integer.MIN_VALUE; max=Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
num[i][0] = sc.nextInt();
num[i][1] = sc.nextInt();
}
Arrays.sort(num, new Comparator<int[]>() {
public int compare(int[] t1, int[] t2) {
if(t1[0] == t2[0]) {
return t1[1] - t2[1];
}
else {
return t1[0] - t2[0];
}
}
});
int cnt = 0;
for(int i=0; i<N; i++) {
int left, right;
left = num[i][0]; right = num[i][1];
changeValue(i, left, right); cnt++;
if(i!=0 && min != num[i-1][0]) {
if(max < right) {
if(Answer < --cnt) Answer = cnt;
cnt = 1;
max = right;
}
}
else if(min > max) {
if(Answer < --cnt) Answer= cnt;
cnt = 0;
}
}
if(Answer < cnt) Answer = cnt;
System.out.println("Case #"+(test_case+1));
System.out.println(Answer);
}
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Solution {
static int Answer;
static int min, max;
static void changeValue(int n, int left, int right) {
if(min < left) min = left;
if(max > right) max = right;
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 1~20
for(int test_case = 0; test_case < T; test_case++) {
Answer = 0;
int N = sc.nextInt(); // 1~100000
int[][] num = new int[N][2]; //-10000000 ~ 10000000
int[][] prev = new int[N][2];
int[] prev_cnt = new int[N];
min=Integer.MIN_VALUE; max=Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
num[i][0] = sc.nextInt();
num[i][1] = sc.nextInt();
}
Arrays.sort(num, new Comparator<int[]>() {
public int compare(int[] t1, int[] t2) {
if(t1[0] == t2[0]) {
return t1[1] - t2[1];
}
else {
return t1[0] - t2[0];
}
}
});
int cnt = 0;
for(int i=0; i<N; i++) {
int left, right;
left = num[i][0]; right = num[i][1];
boolean flag = false;
changeValue(i, left, right); cnt++;
if(i!=0 && min != num[i-1][0]) {
if(max < right) {
if(Answer < --cnt) Answer = cnt;
cnt = 1; flag = true;
max = right;
}
}
else if(min > max) {
if(Answer < --cnt) Answer= cnt;
cnt = 1;
flag = true;
}
if(flag) {
for(int j=i-2; j>=0; j--) {
if(right <= prev[j][1]) {
cnt = prev_cnt[j]+1; break;
}
}
}
prev[i][0] = left; prev[i][1]= right; prev_cnt[i] = cnt;
}
if(Answer < cnt) Answer = cnt;
System.out.println("Case #"+(test_case+1));
System.out.println(Answer);
}
}
}
코드 설명
처음에는 예외처리없이 시간만 보려고 제출했는데 시간은 1초대로 통과했다.
그 다음에 추가로 탐색하는 것을 넣었더니 시간 초과…………….ㅂㄷㅂㄷ
오류를 수정하려고 제일 차이가 안나는 구간으로 돌아가서 그 구간의 폐구간 개수를 받아와서 거기서부터 다시 탐색하는 걸 추가했는데 시간 초과ㅠㅠ
테스트 케이스는 통과하는데 어느 부분에서 시간을 줄여야하는지 모르겠다