[투포인터][Java][BOJ] #2470. 두 용액

#투포인터  #Gold5

https://www.acmicpc.net/problem/2470

🌷 문제 설명

✏️ 백준 연습문제: #2470. 두 용액
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다. 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

⌨️ 입력
첫째 줄에는 전체 용액의 수 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
3 -5 -2 -1	-2 -1
4 0 0 5 5	0 0

 

💡 해결 포인트

1.  투포인터 Reverse Pointers
- 오름차순으로 정렬된 배열
- left와 right의 합이 타겟값보다 작으면, left를 우측(+1)으로 옮긴다(크게 만든다)
- left와 right의 합이 타겟값보다 크면, right를 좌측(-1)으로 옮긴다(작게 만든다)

2. 범위
- 두 특성값의 합의 절댓값이 최대로 클 때: 2,000,000,000

 

정리를 예쁘게 잘 해 준 과거의 나 고마워... 사실 투포인터까지 밖에 모르는데.. 이제 밑천 다 드러났다. 다음 주가 두려울 뿐

[Algorithm I][JavaScript] 투포인터 기법(Two Pointers)

 

🌷 내 코드

1. 투포인터

import java.io.*;
import java.util.*;

public class BOJ_2470 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // N 입력
    int N = Integer.parseInt(br.readLine());

    // N개 용액 입력
    int[] numbers = new int[N]; 
    String [] secondLine = br.readLine().split(" ");
    for (int i = 0; i < N; i++) {
      numbers[i] = Integer.parseInt(secondLine[i]);
    }

    // 배열 정렬
    Arrays.sort(numbers);

    // 투 포인터
    int left = 0;
    int right = N-1;
    int sum = 2000000000; // 두 용액의 합의 최댓값
    int[] answer = new int[2];

    while (left < right) {
      int temp = numbers[left] + numbers[right];

      if (Math.abs(temp) < Math.abs(sum)) {
        sum = temp;
        answer[0] = numbers[left];
        answer[1] = numbers[right];
      } 

      if (temp < 0) { // 두 용액의 합이 0보다 작으면
        left++;
      } else {
        right--;
      }
    }

    System.out.println(answer[0] + " " + answer[1]);
  }
}

 

🌷 코멘트

처음엔 투포인터가 정확히 뭐였는지 이해 없이 그냥 포인터 두개로 모든 경우의 수를 확인해 보려 했다.
당연히 모든 반례는 맞는데 백준 돌려보니 자꾸 시간초과가 났음.

혼자 머리 뜯고 있으니까 혈육이 지나가면서 투포인터의 목적은 100개를 보면 50개만 보려고 하는거라 해서 깨달았음
아 그렇지 그런 가정이 성립하려면 이거 정렬된 배열에서 해야하는거지. (일주일 내내 이진탐색 푼 사람이 맞습니다)

그래서 깨달음을 얻었다고 생각하고 엄청 기대하면서 제출했는데.. 이제 시간초과는 안나는데 자꾸 틀렸다고 그러는거다ㅠㅠ
진짜 이해가 안가서 질문게시판의 반례를 엄청 다 집어넣어봤던 것 같다. 근데 다 돌아가서 더 미칠지경

걍 이제 gpt 돌리려고 생각하고 마지막으로 하품해가면서 첨부터 코드 보는데
불현듯 sum 값을 용액 하나의 최댓값인 1,000,000,000으로 넣어놓은게 눈에 보였다.
두 용액의 합이면.. 당연히 2배인 것을.. 멍청.. sum 값 변경했더니 답이 맞았다 주룩 이제 잘거다ㅠㅜ

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com

 

qminlee723 - Overview