https://www.acmicpc.net/problem/7453
문제를 풀면서 그 전문제에 투포인터로 시간 복잡도를 낮출 수 있는 방법을 배워 그것을 활용해 풀었다.
하지만 시간 복잡도가 아직도 컸다.
최초 코드를 보면서 분석해보자
public class Main {
static long count;
static int[] A, B, C, D;
static int N;
static List<Integer> AB, CD;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
A = new int[N];
B = new int[N];
C = new int[N];
D = new int[N];
AB = new ArrayList<>();
CD = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
B[i] = Integer.parseInt(st.nextToken());
C[i] = Integer.parseInt(st.nextToken());
D[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
AB.add(A[i] + B[j]);
CD.add(C[i] + D[j]);
}
}
Collections.sort(AB);
Collections.sort(CD);
findAnswer();
System.out.println(count);
}
}
해당 문제에서 전혀 감을 잡을 수 없었다.
그래서 구글링을 했다..
구글링에서 찾은 로직도 나와 큰 차이가 없는 것이다..
근데 왜 나만 시간 초과인데...
하지만 그들과 나의 차이점은 단 하나
AB, CD를 리스트가 아닌 int[]로 선언하는것..
그정도가 차이 난다고? 하면서 반신반의하며 수정해서 제출한 결과..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static long count;
static int[] A, B, C, D;
static int N;
static int[] AB, CD;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
A = new int[N];
B = new int[N];
C = new int[N];
D = new int[N];
AB = new int[N * N];
CD = new int[N * N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
B[i] = Integer.parseInt(st.nextToken());
C[i] = Integer.parseInt(st.nextToken());
D[i] = Integer.parseInt(st.nextToken());
}
int idx = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
AB[idx] = A[i] + B[j];
CD[idx++] = C[i] + D[j];
}
}
Arrays.sort(AB);
Arrays.sort(CD);
findAnswer();
System.out.println(count);
}
/**
* 4000 * 4000 * 2 = 16_000_000 * 2 * 2
*/
private static void findAnswer() {
int pointL = 0;
int pointR = CD.length - 1;
while (pointL < AB.length && pointR >= 0) {
int valL = AB[pointL];
int valR = CD[pointR];
if (valL + valR == 0) {
long cntL = 0;
long cntR = 0;
while (pointL < AB.length && valL == AB[pointL]) {
cntL++;
pointL++;
}
while (pointR >= 0 && valR == CD[pointR]) {
cntR++;
pointR--;
}
count += cntL * cntR;
}
else if (valL + valR < 0) {
pointL++;
}
else {
pointR--;
}
}
}
}성공...? 그것도 4초로 기준인 12초에 넉넉하게 성공했다..
왜,,, 어째서..? 라는 고민으로 열심히 공부했다..
내가 생각한 차이가 날것 같은 경우의 수는 4개
1. 리스트는 Integer 타입이고 AB[i] + CD[j]는 int 타입이다. 따라서 List에 넣기 위해서는 N^2번의 boxing이 필요하다.
2. 리스트를 add하는 과정에서 동적 할당이기 때문에 정적인 배열보다 데이터를 넣는데 많은 시간이 걸린다.
3. List의 정렬 방식인 Collections.sort와 int[]의 정렬 방식인 Arrays.sort 사이의 시간 차이가 존재
4. list를 읽는 시간과 배열을 읽는 시간이 차이가 난다.. (사실 이건 둘다 인덱스로 찾는거라서 아닐거라 생각했지만..)
따라서 실험을 시작했다..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Time;
import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.*;
public class Main {
static long count;
static int[] A, B, C, D;
static int N;
// List<Integer> AB, CD;
static int[] AB2, CD2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
A = new int[N];
B = new int[N];
C = new int[N];
D = new int[N];
AB2 = new int[N * N];
CD2 = new int[N * N];
// AB = new ArrayList<>();
// CD = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
B[i] = Integer.parseInt(st.nextToken());
C[i] = Integer.parseInt(st.nextToken());
D[i] = Integer.parseInt(st.nextToken());
}
System.out.println("inputStart" + LocalDateTime.now());
int idx = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// AB.add(A[i] + B[j]);
// CD.add(C[i] + D[j]);
AB2[idx] = A[i] + B[j];
CD2[idx++] = C[i] + D[j];
}
}
System.out.println("inputEnd" + LocalDateTime.now());
System.out.println("sortStart" + LocalDateTime.now());
// Collections.sort(AB);
// Collections.sort(CD);
Arrays.sort(AB2);
Arrays.sort(CD2);
System.out.println("sortEnd" + LocalDateTime.now());
System.out.println("answerStart" + LocalDateTime.now());
findAnswer();
System.out.println("answerEnd" + LocalDateTime.now());
System.out.println(count);
}
/* private static void findAnswer() {
int pointL = 0;
int pointR = CD.size() - 1;
while (pointL < AB.size() && pointR >= 0) {
int valL = AB.get(pointL);
int valR = CD.get(pointR);
if (valL + valR == 0) {
long cntL = 0;
long cntR = 0;
while (pointL < AB.size() && valL == AB.get(pointL)) {
cntL++;
pointL++;
}
while (pointR >= 0 && valR == CD.get(pointR)) {
cntR++;
pointR--;
}
count += cntL * cntR;
}
else if (valL + valR < 0) {
pointL++;
}
else {
pointR--;
}
}
}*/
private static void findAnswer() {
int pointL = 0;
int pointR = CD2.length - 1;
while (pointL < AB2.length && pointR >= 0) {
int valL = AB2[pointL];
int valR = CD2[pointR];
if (valL + valR == 0) {
long cntL = 0;
long cntR = 0;
while (pointL < AB2.length && valL == AB2[pointL]) {
cntL++;
pointL++;
}
while (pointR >= 0 && valR == CD2[pointR]) {
cntR++;
pointR--;
}
count += cntL * cntR;
}
else if (valL + valR < 0) {
pointL++;
}
else {
pointR--;
}
}
}
}
두개를 비교해서 시간을 찍어본 결과
List
inputStart2024-07-20T15:52:43.068120400
inputEnd2024-07-20T15:52:43.592898600
sortStart2024-07-20T15:52:43.592898600
sortEnd2024-07-20T15:52:43.624976500
answerStart2024-07-20T15:52:43.624976500
answerEnd2024-07-20T15:52:43.668397900
int[]
inputStart2024-07-20T15:55:31.212630600
inputEnd2024-07-20T15:55:31.280144400
sortStart2024-07-20T15:55:31.280144400
sortEnd2024-07-20T15:55:31.341669800
answerStart2024-07-20T15:55:31.342170100
answerEnd2024-07-20T15:55:31.358169700
횟수마다 오차가 있을 수는 있지만 큰 차이를 둔 점은 input 항목이다.
전혀 생각을 못했다.. 당연히 Sort과정에서 그런줄 알았는데
찾아본 결과..
Collections.sort안에는 결국 Arrays.sort가 존재한다.
그리고 arrays.sort 다음과 같다.
오호 이래서 reference 타입을 사용하는 List일 때 sort 비용이 primitive 타입을 사용하는 int[]의 sort보다 유일하게 짧았던 것이다.
출처 : https://codingnojam.tistory.com/38
[Java] Arrays.sort()와 Collections.sort()에 대해서 자세히 알아보자!
안녕하세요 coding-knowjam입니다. 오늘은 정렬할 때 사용하는 대표적인 메서드 Arrays.sort()와 Collections.sort()에 대해 알아보겠습니다. 1. Arrays.sort() 1.1 API 문서 (Java 8) 문서 URL : https://docs.oracle.com/javase/8
codingnojam.tistory.com
아무튼..! 그래서 가장 차이가 나는 경우는 input과 관련된 시간이다..
그럼 가정중에 해당하는 것은
1. 리스트는 Integer 타입이고 AB[i] + CD[j]는 int 타입이다. 따라서 List에 넣기 위해서는 N^2번의 boxing이 필요하다.
2. 리스트를 add하는 과정에서 동적 할당이기 때문에 정적인 배열보다 데이터를 넣는데 많은 시간이 걸린다.
이렇게 두개다..!
그럼 이 두개중에 어떤걸까..
실험하기 위해 최초 동적배열 크기를 고정하는 List를 사용해 다시 실험했다.
AB = new ArrayList<>(N * N);
CD = new ArrayList<>(N * N);
이때 시간 계산은 다음과 같다.
inputStart2024-07-20T16:18:19.065689500
inputEnd2024-07-20T16:18:19.220753500
sortStart2024-07-20T16:18:19.221254500
sortEnd2024-07-20T16:18:19.253755200
answerStart2024-07-20T16:18:19.253755200
answerEnd2024-07-20T16:18:19.294755300기존 List의 input인 0.53과 비교해 0.16으로 1/3 정도 줄었다. 0.07인 int[]보다는 2배 많다.
따라서 배열의 크기가 동적할당 됨에 따라 많은 시간이 걸리고 boxing하는 비용도 많이 차지 한다는 걸 알수 있었다.
그래서 혹시 몰라 고정된 동적할당을 한 코드를 제출해보니
그래도 안됨... 그냥 int[] 쓸게요...
'백준문제풀이' 카테고리의 다른 글
| Q. 1644 소수의 연속 합(feat. 투포인터) (0) | 2024.11.25 |
|---|---|
| 위상정렬 알고리즘(Topology Sort) (0) | 2024.07.24 |
| 백준 2133 오답풀이 (0) | 2024.06.12 |
| 2022.06.30 백준 Q2178 (0) | 2022.06.30 |
| 2022.06.29 백준 Q1927 (0) | 2022.06.30 |
