[26주차_목요일] 합이 0

[KodaHye]

• 사이트: 백준(BOJ)
• 문제: 합이 0
• 번호: 3151

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• $1 ≤ N ≤ 10000$
• 배열을 정렬할 뒤, 처음 두 개의 수를 고정하고 세 번째 수를 이분탐색하면서 합이 0이 되는 경우의 수를 구할 수 있을 것 이라고 생각함
  • 처음 두 개의 수 정하기: $10000 × 10000$
  • 세번째 수 이분탐색 진행하기: $log_{2}10000$
  • $1.3 × 10^9$이지만 세번째 수가 이분탐색하는 범위가 계속해서 줄어들기 때문에 일단 시도해봄

💡 풀이 아이디어

처음 두 개의 수를 고정하고, 세 번째 수를 이분탐색을 통해 움직여보면서 세 수의 합이 0이 될 수 있는 경우의 수 구하기

1. 정렬하기: Arrays.sort(arr)
2. 처음 두 개의 수를 고정하고, 세 번째 수 이분탐색 진행

   for(int i = 0; i < arr.length - 2; i++) {
   	for(int j = i + 1; j < arr.length - 1; j++) {
   		
   		// i와 j가 정해졌다면 세 번째 idx에 대해 이분탐색 진행
   		// idx가 가능한 범위에서 upperbound와 lowerbound를 구해서 합이 0이 되는 경우 구하기
   		int s = j + 1, e = arr.length - 1;
   		
   		int sumFirstAndSecond = arr[i] + arr[j];
   		
   		int upper = getUpperBound(arr, sumFirstAndSecond, s, e);
   		int lower = getLowerBound(arr, sumFirstAndSecond, s, e);
   		
   		if(sumFirstAndSecond + arr[upper] != 0) continue;
   		
   		result += upper - lower + 1;
   	}
   }

   • upperbound - lowerbound + 1을 해서 범위에 속하는 숫자의 개수 구하기

• 주의점
  • upperbound와 lowerbound를 구할 때, 범위가 i, j보다 작아지지 않도록 해야 됨
  • $_{10000}C_3$이 int 범위를 벗어나기 때문에 long으로 선언하기

첫 번째 수만 고정하고 두 번째 세 번째 수들을 움직이면서 풀이하면 시간을 더 효율적으로 사용할 수 있네요!!
그리고 DP 같은 방식도 있는 것 같네요! 한 번 공부해보겠습니다!

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 10000
  -10000 ≤ Ai ≤ 10000
• 이중for문 (1000^2)
• 이분탐색(NlogN)
• 10000C3 이므로 정답 반환 배열 long으로 설정

💡 풀이 아이디어

• a+b = -c 형태로 두개를 먼저 정하고 하나 구하기
• a+b : 이중for문 (1000^2)
• c : 이분탐색(NlogN)
  • 이때, 같은 수들이 중복해서 있을 수가 있음
  • 따라서, lowerbound, upperbound를 각각 구해서 둘의 차이로 같은 수가 있는 경우를 더해줌

  Arrays.sort(arr);
  
  long cnt = 0;
  for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
          int left = lowerBound(j + 1, (arr[i] + arr[j]) * -1);
          int right = upperBound(j + 1, (arr[i] + arr[j]) * -1);
          cnt += right-left;
      }
  }
  System.out.println(cnt);

[jmxx219]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 10,000
• 완전 탐색으로 팀원 세명을 뽑는 경우, 시간 초과 발생
• 두 명을 미리 픽해두고, 나머지 한 명을 이분 탐색으로 찾기 -> O(N * N * logN)

💡 풀이 아이디어

• 두 팀원을 고정해두고, 나머지 팀원 한 명은 이분탐색으로 찾기
• 이때 lowerBound와 upperBound로 타켓 갯수 구하기

private static long solve() {
	Arrays.sort(A);
	long count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int target = 0 - (A[i] + A[j]);
			int lowerIndex = lowerBound(j + 1, target);
			int upperIndex = upperBound(j + 1, target);
			count += upperIndex - lowerIndex;
		}
	}
	return count;
}

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 10,000

=> O(N^2) or O(NlogN)으로 생각해볼 수 있음

💡 풀이 아이디어

• 정렬 후, 투포인터를 통해 첫번째 수를 제외한 구간에서 나머지 두 수의 합 == -(첫번째 수)를 만족하는 부분 찾기
• -(첫번째수) = 두 수의 합
• 투 포인터 알고리즘으로 합이 -arr[i(첫번째 수)] 인 요소들(두 수)을 구함
• 세 수의 합이 0인 경우

                int s = arr[start] + arr[end];
                // 세 수의 합이 0이됨
                if (s == -arr[i]) {
                	// start와 end가 같으면 두 수 사이에 있는 조합을 구함
                    if (arr[start] == arr[end]) {
                        ans += (end - start);
                        start++;
                    } 
                    // start와 end가 같지 않으면 각각 이동 시켜 가능한 값 구함
                    else {
                        int a = start, b = end;
                        // start와 같은 최대 값을 찾기 위해 a증가
                        while (a < end && arr[a] == arr[start]) {
                            a++;
                        }
                        // end와 같은 최소 값을 찾기 위해 b감소
                        while (b > start && arr[b] == arr[end]) {
                            b--;
                        }
                        // 경우의 수 == (a ~ start의 개수) * (end ~ b의 개수)
                        ans += (a - start) * (end - b);
                        start = a;
                        end = b;
                    }
                } 

• 0이 아닌 경우

                // 두 수의 합이 -(첫번쨰 수)보다 작음 : 합 증가해야 함
                else if (s < -arr[i]) {
                    start++;
                } 
                // 두 수의 합이 -(첫번째 수)보다 큼 : 합을 감소해야 함
                else {
                    end--;
                }

이분탐색으로 풀면 더 깔끔하게 풀리네요!

[jewan100]

🤔 시간복잡도 고려사항

• $1 \le N \le 10,000$ → 최대 $O(N^2)$

💡 풀이 아이디어

• 가능한 모든 조합을 체크하는 문제

• 가장 편한 방법은 3중 for문으로 해결하는 것

  • $O(N^3)$으로는 해결이 불가능

• 하나의 값을 고정해두고 가능한 범위를 체크하는 방식으로 진행

  • 기준이 되는 값을 하나 정해두고 그 값을 0으로 만들 수 있는 범위를 찾아주기

• 메인 로직

  long cnt = 0;
  for (int i = 0; i < n - 1; i++) {
      if (arr[i] > 0)
          break;
      for (int j = i + 1; j < n; j++) {
          int target = arr[i] + arr[j];
          int upperIndex = getBound(j + 1, -target, true);
          int lowerIndex = getBound(j + 1, -target, false);
          cnt += upperIndex - lowerIndex;
      }
  }

• 매개변수 탐색 → flag를 이용해서 upper인지 lower인지 판단

  private static int getBound(int s, int target, boolean flag) {
      int l = s, r = n;
      while (l < r) {
          int mid = (l + r) / 2;
          if (arr[mid] < target || (flag && arr[mid] == target)) {
              l = mid + 1;
          } else {
              r = mid;
          }
      }
      return l;
  }

뭔가 이상하게 작성했는데 통과해서.. 패스~!