[JAVA] 백준 2470 두 용액 - 골드5

 

실버문제를 어느정도 풀어봤으니 이제 sorting 관련 골드 문제를 풀려고한다!

 

 

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

2470번: 두 용액

 

• 10억까지 정수로 나타내지고, 합은 최대 20억정도가 될 수 있으니 int값에 저장할 수 있음

 

 

처음 생각한 풀이(시간초과)

• 음수값을 저장하는 배열과 양수값을 저장하는 배열을 만들어 정렬한다
• 인덱스로 비교비교하면서 차이가 0에 가까운 애를 result에 저장한다
• 양수값이 하나도 없다면 가장 값이 큰 음수값 2개를 더하고, 음수값이 없을 때도 거의 마찬가지로 가장 값이 작은 양수값 2개를 더하는 식으로 구현하려고 한다.
• 결과: 시간초과남

 

 

두 번째 생각한 풀이(복잡함)

• 비교할 값을 찾는 방식을 바꿔보려고 한다
• 모든 값을 일단 정렬한다
• 모든 음수값에 대해 나보다 큰 값 중 내 절댓값과 가장 가까운 값을 구한다(차이가 가장 적음)
  
  • 양수값일 경우 따로 처리를 해줬다
• 차이가 가장 최소인 애를 구한다
• 물론 더 좋은 이진탐색 풀이를 사용하면 복잡하지 않음 -> 참고하기 좋은 블로그: https://yanoo.tistory.com/97

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    int[] arr = new int[cnt];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < cnt; i++)
      arr[i] = Integer.parseInt(st.nextToken());

    //오름차순 정렬
    Arrays.sort(arr);

    int minDiff = Integer.MAX_VALUE;
    int resultSmall = 0;
    int resultBig = 0;
    Integer firstPlusVal = null;

    for (int i = 0; i < cnt; i++) {
      int now = arr[i];

      //양수값 발견 시 처리
      if (now > 0) {
        if (firstPlusVal == null) {
          firstPlusVal = now;
          continue;
        } else {
          if (minDiff > firstPlusVal + now) {
            minDiff = firstPlusVal + now;
            resultSmall = firstPlusVal;
            resultBig = now;
          }

          break;
        }
      }

      if (i == arr.length-1)
        break;

      //절댓값과 가장 가까운 값 찾기
      int tmp = binary_search(-now, i + 1, arr);

      int sum = Math.abs(now + tmp);
      if (minDiff > sum) {
        minDiff = sum;
        resultSmall = now;
        resultBig = tmp;
      }
    }

    System.out.println(resultSmall + " " + resultBig);
  }

  //target과 가장 가까운 값 찾기
  public static int binary_search(int target, int start, int[] arr) {
    int end = arr.length;

    while (start < end) {
      int mid = (start + end) / 2;

      if (arr[mid] == target) {
        return arr[mid];
      } else if (arr[mid] < target) {

        if (mid == arr.length-1) {
          return arr[mid];
        } else if (arr[mid+1] > target) {
          int diff = Math.abs(-target + arr[mid+1]);
          int diff2 = Math.abs(-target + arr[mid]);
          if (diff < diff2)
            return arr[mid+1];
          else
            return arr[mid];
        }

        start = mid + 1;
      } else { //arr[mid] > target
        end = mid;
      }
    }

    return arr[start];
  }
}

• 예외처리 때문에 코드가 많이많이 길어졌다..
• 이진탐색을 위해 오름차순 정렬을 해준다
• 인덱스 0부터 arr.length-1까지 값을 하나씩 빼면서 처리해준다
  • 양수를 2회 이상 발견 시 양수 2개를 더한 값과 minDiff를 비교하여 minDiff를 갱신하고 for문을 빠져나간다
  • 뽑은 값은 음수값일 것이기 때문에 내 절댓값과 가장 가까운 값을 찾는 함수를 호출한다
  • 절댓값과 가장 가까운 값과 나의 합을 구해 minDiff와 비교 후 갱신한다
• 내 절댓값과 가장 가까운 값은 이진탐색 방법으로 찾는다
  • 예를 들어 5를 찾는 경우에 return은 다음과 같이 4가지경우에 할 수 있다
  • 1234 -> 4
  • 678 -> 6
  • 156 -> 5
  • 237 -> 3 or 7
• 이진탐색을 할 때 찾는 리스트에 내가 없을 때, 나와 가장 가까운 값을 찾는 느낌이다.

 

 

더 좋은 풀이

• 다른 더 좋은 풀이를 구글링으로 찾아 해당 방식으로 구현해봤다
  • 참고 블로그: https://maivve.tistory.com/129
• 모든 값을 오름차순 정렬한다
• small과 big 포인터로 양 끝을 가리킨다
• small < big 일 때 반복문을 수행한다
  • arr[small] + arr[big]의 절댓값을 구하여 minDiff와 비교 후 더 작은 값으로 갱신한다
  • 만약 arr[small]의 절댓값이 arr[big]의 절댓값보다 작다면 big에 -1을 해주고, 그 반대면 small에 +1을 해준다
  • (차이가 0 이상인지 확인하여 -1 +1을 해줘도 됨)

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    int[] arr = new int[cnt];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < cnt; i++)
      arr[i] = Integer.parseInt(st.nextToken());

    //오름차순 정렬
    Arrays.sort(arr);

    int small = 0;
    int big = arr.length-1;
    int minDiff = Integer.MAX_VALUE;
    int resultSmall = 0;
    int resultBig = 0;

    while (small < big) {
      int tmpDiff = Math.abs(arr[small] + arr[big]);
      if (tmpDiff < minDiff) {
        minDiff = tmpDiff;
        resultSmall = arr[small];
        resultBig = arr[big];
      }

      if (Math.abs(arr[small]) < Math.abs(arr[big]))
        big--;
      else
        small++;
    }

    System.out.println(resultSmall + " " + resultBig);
  }
}

• small, big으로 양 끝 가리킴
• minDiff: 두 수의 합의 절댓값의 최솟값
• resultSmall: 두 수 중 작은 애
• resultBig: 두 수 중 큰 애

 

 

 

마지막 풀이에 대한 아이디어를 생각못해서 삽질을 했다 ㅠㅠ

특히 이진탐색으로 구현할 때 조건 몇 개를 자꾸 빠뜨려서 너무 고생했다.. 다음엔 이진탐색 문제를 더 많이 풀어보려고 한다