백준 3151 자바

문제

합이 0

처음 풀이는 세수합(백준 2295)문제와 비슷해보여 이분탐색으로 풀었으나 답이 여러개 있을경우 하나만 선택하는 문제로 틀렸다. 그래서 다시 풀어가는 과정의 정리와 간단한 코드로 구현하고자 글을 남기고 싶었습니다.

풀이과정

1. 시간복잡도

   • n이 10000이기 때문에 n^3은 시간초과가 걸린다

   • 그로인해 정렬(n)과 이분탐색(logN)으로 이분탐색을 선택하게 되었습니다

2. 3세수의 합이 0인 수 찾기

   2.1 먼저 정렬을 해준다

   2.2 x+y+z =0 이지만 3중 for문은 시간초과로 x+y=-z가 될 수 있도록 2중 for문을 돌려 확인한다. 세수합(백준 2295) 비슷

   2.3 단순 이분탐색으로 풀게되면 한가지의 수를 찾게 된다. 하지만 1,2,2,2,3일 경우 답의 2의 수가 한가지가 아니고 3가지 이므로 lower, upper 방식을 사용한다. 해당 방식이 익숙하지 않다면 백준10816(숫자카드2)부분을 이해하고 풀면 간단하게 이해할 수 있습니다.

• lower, upper쓰는 이유
  

• y의 값이 2이기 때문에 lower의 위치로 값이 3개
  

⛳ 내가 작성한 코드

import java.util.*;
public class A3151 {
	static int[] list;
	public static void main(String[] args) throws NumberFormatException, IOException {
	
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());

      list = new int[n];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<n; i++) {
          list[i] = Integer.parseInt(st.nextToken());
      }

      //1. 정렬
      Arrays.sort(list);
      long ans = 0;

      //2. 3수의 합이 0인 수 찾기 x+y=-z
      for(int i=0; i<n; i++) {
          for(int j=i+1; j<n; j++) {
              //3. 정답이 되는 처음 인덱스
              int start = lower(j+1, n, (list[i]+list[j])*-1);

              //4. 정답이 되는 마지막 인덱스
              int end = upper(j+1, n, (list[i]+list[j])*-1);

              //5. 마지막과 처음 인덱스의 합
              ans += (end-start);
          }
      }

      System.out.println(ans);
  }
  //z의 값의 처음 인덱스 구하기
  private static int lower(int start, int end, int tmp) {

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

          if(list[mid]>=tmp) {
              end = mid;
          }else {
              start = mid+1;
          }
      }
      return start;
  }
  //z의 값의 마지막 인덱스 구하기
  private static int upper(int start, int end, int tmp) {

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

          if(list[mid]>tmp) {
              end = mid;
          }else {
              start = mid+1;
          }
      }
      return start;
  }
}