-
[백준] 2470 두 용액 - Java알고리즘 문제 풀이 2024. 4. 22. 16:53
문제 - 두 용액
https://www.acmicpc.net/problem/2470
문제 설명
입력
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
예제 입력
5 -2 4 -99 -1 98
예제 출력
-99 98
접근 방법
- 시간 제한이 1초라 일반 탐색으로는 문제를 풀기가 힘들 것 이다
- 그래서 이분 탐색으로 문제를 풀것이다
- 문제를 이해 하자면 배열의 요소 중에서 서로 다른 요소를 덧셈을 하여 그 결과의 절댓값이 제일 적은 것을 찾는 문제이다
- 그래서 이 문제는 pointer로 문제를 풀어야 하는데 이 말은 즉, 배열의 인덱스를 left 와 right 초기값으로 잡고 풀어야한다
코드 작성
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int N = Integer.parseInt(br.readLine()); if (2 > N || N > 100000) { throw new RuntimeException("N 입력을 다시하세요"); } StringTokenizer st = new StringTokenizer(br.readLine()); List<Integer> list = new ArrayList<>(); for (int i = 0; i < N; i++) { list.add(Integer.parseInt(st.nextToken())); } list.sort(Comparator.comparingInt(Integer::intValue)); int left = 0; int right = N - 1; int min = Integer.MAX_VALUE; int[] result = new int[2]; while (left < right) { int sum = list.get(left) + list.get(right); if (min > Math.abs(sum)) { min = Math.abs(sum); result[0] = list.get(left); result[1] = list.get(right); if (sum == 0) { break; } } if (sum < 0) { left++; } else { right--; } } System.out.println(result[0] + " " + result[1]); } } }
풀고 느낀점
1. 이 문제의 핵심은 절댓값을 어떤식으로 사용하느냐 같다
2. 일반적인 이분 탐색 문제이다
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 1966 프린터 큐 - Java (0) 2024.04.25 [백준] 2161 카드1 - Java (0) 2024.04.24 [프로그래머스] 카드 뭉치 - Java (1) 2024.04.22 [프로그래머스] 부족한 금액 계산하기 - Java (0) 2024.04.21 [프로그래머스] H-Index -Java (0) 2024.04.19