https://www.acmicpc.net/problem/2470
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00
www.acmicpc.net
오늘 두번째로 풀어본 문제는 약 한달전 풀었다가 실패했던 두 용액이라는 문제이다.
규칙은 간단하다. 두 용액 값을 더하여 0에 가장 가까운 두 용액을 찾는 문제다.
호기롭게 도전했던 지난달, 시간초과라는 쓴맛을 맛봤다..
기본적으로 이분 탐색 방법을 사용하여 문제를 풀었다. 첫 도전때 실패 원인은 쓸데없이 많이 발생하는 연산 문제이다.
그래서 이분탐색 부분을 다시 작성하여 코드 길이가 842에서 648로 줄었다. 그러나 여전히 실패
살짝 눈물이 나려고했다. 그래서 잠시 덮어 놨다가 까먹고 오늘 다시 풀게됬다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];
for(int i = 0; i<N; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int left = 0;
int right = N-1;
int minLeft = 0;
int minRight = N-1;
int min = 2000000000;
while(left < right) {
int ans = a[left]+a[right];
if(min > Math.abs(ans)){
min = Math.abs(a[left]+a[right]);
minLeft = a[left];
minRight = a[right];
}
if(ans > 0) right--;
else left++;
}
System.out.println(minLeft+" "+minRight);
}
}
이렇게 코드를 수정했지만 시간 초과가 나서 질문 검색을 보다가 내장함수 sort가 아닌 병합 정렬을 사용해보기로했다.
import java.util.*;
import java.io.*;
public class Main {
static int[] a;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
a = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i = 0; i<N; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
sort(a, 0, N);
int left = 0, right = N-1;
int minLeft = 0, minRight = 0, min = Integer.MAX_VALUE;
while(left < right) {
int ans = a[left]+a[right];
if(min > Math.abs(ans)){
min = Math.abs(ans);
minLeft = a[left];
minRight = a[right];
}
if(ans > 0) right--;
else left++;
}
bw.write(minLeft+" "+minRight);
bw.flush();
bw.close();
br.close();
}
private static void sort(int[] arr, int low, int high) {
if (high - low < 2) {
return;
}
int mid = (low + high) / 2;
sort(arr, 0, mid);
sort(arr, mid, high);
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low];
int t = 0, l = low, h = mid;
while (l < mid && h < high) {
if (arr[l] < arr[h]) {
temp[t++] = arr[l++];
} else {
temp[t++] = arr[h++];
}
}
while (l < mid) {
temp[t++] = arr[l++];
}
while (h < high) {
temp[t++] = arr[h++];
}
for (int i = low; i < high; i++) {
arr[i] = temp[i - low];
}
}
}
그랬더니 메모리 초과라는 눈물겨운 결과와 보기싫은 긴 코드를 보게됬다... 사실 ideone에서 돌렸을때 시간 차이는 그렇게 크지 않았어서 그냥 arrays.sort를 사용하기로 했다..
아래의 코드가 최종 코드이다.
역시나 따로 정렬를 구현하지 않아도 됬다.
io 패키지를 사용해 입출력 시간을 단축하고 쓸데없는 연산을 줄였더니 시간초과 없이 문제를 해결할 수 있었다. 문제를 해결했지만 살짝 힘들어서 눈물이 났다,, 언제쯤,, 안울고 풀수있을까,,
import java.util.*;
import java.io.*;
public class Main {
static int minLeft = 0, minRight = 0, min = 2000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] a = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i = 0; i<N; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(a);
int left = 0, right = N-1;
while(left < right) {
int ans = a[left]+a[right];
if(min > Math.abs(ans)){
min = Math.abs(ans);
minLeft = a[left];
minRight = a[right];
}
if(ans > 0) right--;
else left++;
}
bw.write(minLeft+" "+minRight);
bw.flush();
bw.close();
br.close();
}
}
'today's alogrithm' 카테고리의 다른 글
[프로그래머스] 줄서는 방법 - Java (0) | 2021.08.25 |
---|---|
[BOJ] 4375번 1 - JAVA (0) | 2021.06.25 |
[BOJ] 1212번 8진수 2진수 - JAVA (0) | 2021.06.22 |
[BOJ] 12852번 1로 만들기 2 - JAVA (0) | 2021.06.21 |
[BOJ] 2502번 떡 먹는 호랑이 - JAVA (0) | 2021.06.18 |