문제 링크
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 용액의 특성값은 오름차순으로 주어지며, 알칼리나 산성 용액만 주어질 수 있습니다.
2. 서로 다른 2개의 용액을 합칠 때 0에 가장 가까운 두 용액을 결과로 출력합니다.
3. 0에 가장 가까운 경우가 중복될 경우 아무것이나 하나를 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 두 포인터를 이용하여 용액을 합치는 과정을 탐색합니다.
3. 0에 가장 가까운 경우의 두 용액의 특성값을 결과로 출력합니다.
0에 가장 가까운 두 용액 탐색!
두 용액의 특성값을 합쳤을 때 0에 가까운 값을 확인 : |용액1 특성값 + 용액2 특성값|
오름차순 정렬된 특성값이 주어지기 때문에
두 포인터를 이용하여 가장 큰 값과 가장 작은 값부터 비교하여 줄여나가면서 탐색합니다.
용액을 합쳣을 때 3가지 경우가 존재합니다.
용액1 특성값 + 용액2 특성값 < 0
용액1 특성값 + 용액2 특성값 = 0
용액1 특성값 + 용액2 특성값 > 0
두 포인터 탐색을 진행!
| -2 | --1 | 0 | 3 | 4 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(4)| = 2
현재 가장 가까운 값 : 2
최소 용액(-2) + 최대 용액(4) > 0
: 최대 용액 감소!
| -2 | -1 | 0 | 3 | 4 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(3)| = 1
현재 가장 가까운 값 : 1
최소 용액(-2) + 최대 용액(3) > 0
: 최대 용액 감소!
| -2 | -1 | 0 | 3 | 4 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(0)| = 2
현재 가장 가까운 값 : 1
최소 용액(-2) + 최대 용액(0) < 0
: 최소 용액 증가!
| -2 | -1 | 0 | 3 | 4 |
| 최소 | 최대 |
|최소 용액(-1) + 최대 용액(0)| = 1
현재 가장 가까운 값 : 1
최소 용액(-1) + 최대 용액(0) < 0
: 최소 용액 증가!
최소 용액 == 최대 용액 : 탐색 종료!
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 5
용액 정보
| -99 | -2 | -1 | 4 | 98 |
2. 두 포인터를 이용하여 용액을 합치는 과정을 탐색합니다.
| -99 | -2 | -1 | 4 | 98 |
| 최소 | 최대 |
|최소 용액(-99) + 최대 용액(98)| = 1
현재 가장 가까운 값 : 1
최소 용액(-99) + 최대 용액(98) < 0
: 최소 용액 증가!
| -99 | -2 | -1 | 4 | 98 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(98)| = 96
현재 가장 가까운 값 : 1
최소 용액(-2) + 최대 용액(98) > 0
: 최대 용액 감소!
| -99 | -2 | -1 | 4 | 98 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(4)| = 2
현재 가장 가까운 값 : 1
최소 용액(-2) + 최대 용액(4) > 0
: 최대 용액 감소!
| -99 | -2 | -1 | 4 | 98 |
| 최소 | 최대 |
|최소 용액(-2) + 최대 용액(-1)| = 3
현재 가장 가까운 값 : 1
최소 용액(-2) + 최대 용액(-1) < 0
: 최소 용액 증가!
최소 용액 == 최대 용액 : 탐색 종료!
3. 0에 가장 가까운 경우의 두 용액의 특성값을 결과로 출력합니다.
현재 가장 가까운 값 : 1( -99, 98)
-99 98을 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용해서 용액의 특성값을 띄어쓰기 기준 나누었습니다.
- 두 포인터를 이용하여 최소와 최대를 지정하여 탐색합니다.
- 탐색을 진행할 때 두 용액의 절대값과 합에 따라 최소와 최대에 값들을 변경해줍니다.
- 탐색이 끝난 뒤 0에 가까운 두 용액의 특성값을 결과로 BufferedWriter에 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
List<Integer> list = new ArrayList<>(); //용액 특성값 저장할 리스트
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//입력되는 특성값 저장
for(int i=0; i<N; i++)
list.add(Integer.parseInt(st.nextToken()));
int m_id = 0, p_id = N-1; //m_id : 최소 인덱스, p_id : 최대 인덱스
//0에 가까운 두 용액!
int n1 = 0, n2 = 0;
int max = Integer.MAX_VALUE;
//두 포인터를 이용해 용액 탐색!
while(m_id < p_id){
//현재 가리키는 두 용액 합치기!
int temp = list.get(m_id) + list.get(p_id);
if(max > Math.abs(temp)){ //0에 가장 가까운 값인지 확인
max = Math.abs(temp);
n1 = list.get(m_id);
n2 = list.get(p_id);
}
if(temp > 0) //특성값의 합이 양수일 때 : 최대 용액 감소!
p_id--;
else if(temp < 0) //특성값 합이 음수일 때 : 최소 용액 증가!
m_id++;
else{ //특성합이 0일 때(최상의 경우), 탐색 종료 후 두 용액 출력
n1 = list.get(m_id);
n2 = list.get(p_id);
break;
}
}
bw.write(n1 + " " + n2); //0에 가까운 두 용액 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
}'백준' 카테고리의 다른 글
| [백준] 알고리즘 분류(두 포인터,JAVA)2283번, 구간 자르기 (0) | 2023.02.03 |
|---|---|
| [백준] 알고리즘 분류(그래프 이론,JAVA)1005번, ACM Craft (2) | 2023.02.02 |
| [백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)2531번, 회전 초밥 (0) | 2023.01.31 |
| [백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)2502번, 떡 먹는 호랑이 (0) | 2023.01.30 |
| [백준] 알고리즘 분류(자료구조,JAVA)1918번, 후위 표기식 (0) | 2023.01.29 |
댓글