[백준] 7453번 : 합이 0인 네 정수

[백준] 7453번 : 합이 0인 네 정수

7453번: 합이 0인 네 정수

7453번: 합이 0인 네 정수

📄 문제개요

• 정수로 이루어진 크기가 같은 배열 A, B, C D 가 있다.
• A[a], B[b], C[c], D[d] 합이 0인 (a,b,c,d) 쌍의 개수를 구하는 프로그램을 작성하시오.
• 배열의 크기는 n ( 1≤ n ≤ 4000) 이고, 배열에 들어있는 정수 절대값은 최대 2^28이다.

🤔 문제분석

• 해당문제는 4000 x 4000 x 4000 x 4000 의 경우의 수를 문제를 해결해야함으로, 완전탐색으로는 문제의 해결이 어렵다.
• 이분탐색으로 접근하여 풀어보자.
  • 합이 0인경우
  • 합이 0보다 큰경우
  • 합이 0보다 작은경우
• 합이 0 인경우는 카운팅한다. 해당조합을 visited 배열에 둠으로서 한번더 방문하지 못하게 한다.
• 합이 0보다 큰경우 합을 줄이기위하여 정렬된 해당배열중에서 왼쪽 배열들을 모두 방문해본다.
• 합이 0보다 작은 경우 합을 늘리기위하여 정렬된 해당 배열중에서 오른쪽 배열들을 모두 방문해본다.
• 예를들어 A[1], B[1], C[1], D[1] 이 주어진다면,
  • 0보다 클경우, 이전값에 있는 배열을 만들어서 탐색해본다.
  • 0보다 작을경우, 이후값에 있는 배열의 조합을 만들어서 탐색해본다.
  • 0일경우 모든 경우의수를 다 탐색해보아야한다.
• 문제의 틀을 보면 재귀적으로 호출하여 문제를 해결하면 좋을 것 같다.
• 함수의 파라미터로, a_start, a_end b_start, b_end … 가 주어지고, visited 배열이 주어진다.

📝 의사코드

• 길이의 중간값의 인덱스의 의 합이 0인경우 0보다 큰경우, 0보다 작은경우 분기한다.
• 0인경우, 왼쪽 오른쪽을 모두 탐색한다.
• 0보다 큰경우, 왼쪽을 탐색한다.
• 0보다 작은경우, 오른쪽을 탐색한다.

💻 코드

import sys
input = sys.stdin.readline
N = int(input())
visited = set()

A = []
B = []
C = []
D = []
for _ in range(N):
    temp = list(map(int, input().split()))
    A.append(temp[0])
    B.append(temp[1])
    C.append(temp[2])
    D.append(temp[3])

A.sort()
B.sort()
C.sort()
D.sort()

ans = 0
def solve(a_s, a_e, b_s, b_e, c_s, c_e, d_s, d_e):
    global ans
    if a_s > a_e or b_s > b_e or c_s > c_e or d_s > d_e:
        return
    
    if (a_s, a_e, b_s, b_e, c_s, c_e, d_s, d_e) in visited:
        return
    
    # 방문처리
    visited.add((a_s, a_e, b_s, b_e, c_s, c_e, d_s, d_e))
    
    a_m = (a_s + a_e) // 2
    b_m = (b_s + b_e) // 2
    c_m = (c_s + c_e) // 2
    d_m = (d_s + d_e) // 2

    total = A[a_m] + B[b_m] + C[c_m] + D[d_m]
    if total > 0: # total이 더 클경우
        # 왼쪽을 탐색해본다.
        solve(a_s, a_m-1, b_s, b_e, c_s, c_e, d_s, d_e)
        solve(a_s, a_e, b_s, b_m-1, c_s, c_e, d_s, d_e)
        solve(a_s, a_e, b_s, b_e, c_s, c_m-1, d_s, d_e)
        solve(a_s, a_e, b_s, b_e, c_s, c_e, d_s, d_m-1)
    else:
        if total == 0:
            ans += 1
        # 오른쪽
        solve(a_m+1, a_e, b_s, b_e, c_s, c_e, d_s, d_e)
        solve(a_s, a_e, b_m+1, b_e, c_s, c_e, d_s, d_e)
        solve(a_s, a_e, b_s, b_e, c_m+1, c_e, d_s, d_e)
        solve(a_s, a_e, b_s, b_e, c_s, c_e, d_m+1, d_e)

solve(0, N-1, 0, N-1, 0, N-1, 0, N-1)
print(ans)

🎯 피드백 및 개선사항

• 위의 문제는 시간복잡도 문제로 문제를 해결하지 못하였습니다. ( 많은 재귀로인해 시간복잡도 문제 )
• 문제의 접근을 잘못하였습니다.

<aside> 💡 AB값을 더한 것과 CD값을 더한것을 2개의 자료를 가지고 문제를 해결 할 수 있다.

</aside>

• 딕셔너리를 이용하여 문제를 해결한다. (AB를 더한값과 CD를 더한값을 해시테이블을 사용하여 카운팅한다) O(N^2)으로 문제를 해결 할 수 있다.
• 이분탐색으로 또한 문제를 해결 할 수 있는데, AB, CD를 투포인터 개념을 적용하여, AB - CD 값의 조건에 따라서 왼쪽을 증가하거나 오른쪽을 증가시키고, 만약 AB-CD가 0 이라면 이분탐색으로 개수를 파악하여, index값을 다시 갱신한다. (최선의 경우는 log(N)에 탐색), (최악의 경우 N^2에 탐색)

❓다른사람은 어떻게 풀었을까?

7453. 합이 0인 네 정수 (Python)

딕셔너리를 활용한 문제풀이

• 딕셔너리를 생성한다.
• A,B를 순회하면서 a+b의 값이 key로 갖는 딕셔너리의 개수를 샌다.
• C,D를 순회하면서 만약 -(c+d)의 값이 해시테이블에 존재한다면 카운팅해주면 된다.
• 예를들어 a+b값이 53이고, c+d 값이 -53이라면 둘이 합하면 0이므로 -(c+d)로 부호를 절환하여 체크한다.

from collections import defaultdict
import sys
input = sys.stdin.readline

ab_sum = defaultdict(int)

N = int(input())
A, B, C, D = [], [], [], []
for _ in range(N):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
    
    
for a in A:
    for b in B:
        ab_sum[a+b] += 1

ans = 0
for c in C:
    for d in D:
        ans += ab_sum[-(c+d)]
        
print(ans)

투포인터, 이분탐색을 이용한 문제풀이

• A,B를 순회하면서 AB배열을 만든다. C,D를 순회하면서 CD배열을 만든다.
• left를 0, right를 len(CD)-1를 둠으로서, left는 AB 왼쪽**(가장작은값), right는 CD의 오른쪽(가장큰값)**이다.
• AB[left] + CD[right]를 더해본다.
  • 0보다 작다면 AB의 증가시킨다 ( AB[left] + CD[right] 이 커진다. ) left += 1
  • 0보다 크다면 CD를 감소시킨다. ( AB[left] + CD[right] 이 작아진다.) right -= 1
  • 0이라면 AB와 CD의 해당 숫자의 개수를 카운팅하고, left와 right를 각각 카운팅 한만큼 가중치에 더해주고 left과 right를 바꿔준다.

from bisect import bisect_left
from bisect import bisect_right

import sys
input = sys.stdin.readline

N = int(input())  # 배열의 크기
A, B, C, D = [], [], [], []

for _ in range(N):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
    
AB = []
CD = []
for i in range(N):
    for j in range(N):
        AB.append(A[i]+B[j])
        CD.append(C[i]+D[j])
        

left = 0
right = len(CD) -1
ans = 0
AB.sort()
CD.sort()

while left < len(AB) and right >= 0:
    cost = AB[left] + CD[right]
    # 0보다 클경우 right를 감소시킨다.
    if cost > 0:
        right -= 1
    # 0보다 작을경우 left를 증가시킨다.
    elif cost < 0:
        left += 1
    else:
        # 해당값이 몇개 있는지 카운팅한다.
        ab_new_l, ab_new_r = bisect_left(AB, AB[left]), bisect_right(AB, AB[left])
        cd_new_l, cd_new_r = bisect_left(CD, CD[right]), bisect_right(CD, CD[right])
        ans += (ab_new_r-ab_new_l) * (cd_new_r - cd_new_l)
        left = ab_new_r
        right = cd_new_l - 1
        
print(ans)