본문 바로가기
백준

[백준] 알고리즘 분류(두 포인터,JAVA)2467번, 용액

by 열정적인 이찬형 2023. 2. 2.

문제 링크

 

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
 
: 0에 가까워지려면 특성값이 작은 값이 커져야 합니다.

 

용액1 특성값  + 용액2 특성값 = 0
 
: 이보다 좋은 특성값 존재 X, 현재 두 용액을 결과로 출력!

 

용액1 특성값  + 용액2 특성값 > 0
 
: 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();


    }
}
 

댓글