[알고리즘풀이]백준 2470: 두 용액 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

오랜만에 알고리즘 공부한 걸 올리네요!

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 2470번 두 용액을 풀었습니다. 

2470번: 두 용액

 

본문

1) 문제

 

2) 과정

꽤 긴 시간을 들여서 풀었던걸로 기억하는 문제입니다. (1시간~2시간 정도 썼던 것 같습니다)

이번엔 main에 모두 넣어서 문제를 풀었습니다.

그동안 문제를 풀면서 알고리즘 문제는 input& initialize, logic, output으로 대부분 구성된다는 걸 알게되었습니다.

그래서 이번 정리 또한 위의 3가지로 나누어 설명해보겠습니다.

 

2-1) input  & initialize

 

 

입력이 위와 같기 때문에 먼저 n을 받고, 그 다음엔 띄어쓰기로 나열된 용액의 특성값을 int배열로 변경합니다.

 

읽어오는 것 관련된 정보(BufferedReader, InputStreamReader .etc)는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

 

그리고 Arrays.sort(int배열)을 이용해 이를 정렬합니다.

	// Attribute
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
        // Input
        int n = Integer.parseInt(reader.readLine());

        String[] strArrN = reader.readLine().split(" ");
        int[] intArr = new int[n];
        for(int i = 0; i< n; i++){
            intArr[i]=Integer.parseInt(strArrN[i]);
        }
        
        // Initialize
        Arrays.sort(intArr);
        
        int frontidx=0, endIdx= n-1;
        int max=2000000000;
        int minSide=0, maxSide=0;

 

2-2) Logic

        // Logic
        while(frontidx<endIdx){
            int sum = intArr[frontidx]+ intArr[endIdx];

            if(Math.abs(sum)<max){
                minSide= intArr[frontidx];
                maxSide= intArr[endIdx];
                max=Math.abs(sum);
            }

            if(sum>0) endIdx--;
            else frontidx++;
        }

Logic은 값을 이동하는 부분과 종료조건을 정하는 부분이 있습니다.

 

먼저, 값을 이동하는 부분은 다음과 같습니다. 이미 정렬해둔 intArr의 양끝에서 접근하며, 처음엔 양쪽의 합의 평균이 max인 2000000000(두 용액이 모두 최대값인 1000000000일 경우를 고려)보다 작으면 minSide와 maxSide를 지금 intArr의 맨앞과 맨뒤 값으로 변경하고 max를 지금의 두 용액의 최대값으로 변경해줍니다. 

 

그리고 종료 조건을 셋팅하기 위해 sum이 양수일 경우엔 앞쪽 부분(음수가 있을 확률이 큰 부분)이 더 크기 때문에 양수가 있는 부분인 endIdx를 하나 줄여줍니다. 이와 반대로 sum이 음수일 경우엔 뒤쪽 부분(양수가 있을 확률이 큰 부분)이 더 크기 때문에 이를 줄이고자 frontidx를 하나 더해줍니다. 그렇게 while문을 통해 반복하다 보면 frontidx가 endidx보다 작아지는 부분이 생깁니다. 이 때가 특성값이 0에 가까운 용액을 만들어내는 두 용액의 특성값이 minside와 maxside에 저장되어있을 때입니다.

 

while loop마다 이렇게 값이 이동합니다. (예시)

 

 

2-3) output

        System.out.println(minSide+" "+maxSide);

 

logic의 while loop을 거치며 합이 가장 0에 가까운 두 용액 중 작은 값이 minSide, 큰 값이 maxSide에 저장되었습니다.

 

이를 순서대로 출력합니다.

 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.binarySearch;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class BOJ2470 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        String[] strArrN = reader.readLine().split(" ");
        int[] intArr = new int[n];
        for(int i = 0; i< n; i++){
            intArr[i]=Integer.parseInt(strArrN[i]);
        }
        Arrays.sort(intArr);


        int frontidx=0, endIdx= n-1;
        int max=2000000000;
        int minSide=0, maxSide=0;

        while(frontidx<endIdx){
            int sum = intArr[frontidx]+ intArr[endIdx];

            if(Math.abs(sum)<max){
                minSide= intArr[frontidx];
                maxSide= intArr[endIdx];
                max=Math.abs(sum);
            }

            if(sum>0) endIdx--;
            else frontidx++;
        }
        System.out.println(minSide+" "+maxSide);
    }

}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/edit/master/sujeong/binarySearch/BOJ2470.java

GitHub: Where the world builds software