[BaekJoon] 7453 합이 0인 네 정수

🔦 문제 링크

✍️ 나의 풀이

---

• 모든 조합의 합을 구하면 $O(4000^{4})$이 최악이므로 절대 불가능 하다.
• 따라서, 4개의 숫자를 쪼개 두 개씩 더한 값으로 나눈다.
• 두 개씩 더할 때 순서가 바껴도 상관 없으므로 순열로 계산해야한다.
  -> for i in range(n) for j in range(n)

< 풀이 순서 >
1. 투 포인터를 사용하기 위해 두 리스트를 정렬한다.
2. 두 리스트 값을 더해서 0 이면 각각의 리스트에서 중복되는 값의 갯수를 센다.
3. 0 보다 작으면 더 큰 값을 넣어주기 위해 lp 증가
4. 0 보다 크면 더 작은 값을 넣어주기 위해 rp 증가
5. lp 또는 rp가 리스트의 길이보다 커지면 더 이상 0이 나올 수 없으므로 반복문을 빠져나온다.

🛠 나의 코드

---

import sys
n = int(input())
arr = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
left_arr, right_arr = [], []
for i in range(n):
    for j in range(n):
        left_arr.append(arr[i][0] + arr[j][1])
        right_arr.append(arr[i][2] + arr[j][3])


left_arr.sort()
right_arr.sort()

ans = 0

len_ls, len_rs = len(left_arr), len(right_arr)
lp, rp = 0, len_rs - 1
while lp < len_ls and rp >= 0:
    tmp = left_arr[lp] + right_arr[rp]

    # 더해서 답과 같다면 이제 중복된 값을 계산해줘야 한다.
    if tmp == 0:
        lsame, rsame = 1, 1

        lt, rt = lp, rp  # 투 포인트 사용 시 주의해야할 점
                         # 원하는 합의 위치를 기억해둬야 한다.
        lp += 1
        while lp < len_ls and left_arr[lp] + right_arr[rt] == 0:
            # (소팅된 리스트에서)같은 숫자 갯수 세기
            lsame += 1
            lp += 1

        rp -= 1
        while rp >= 0 and left_arr[lt] + right_arr[rp] == 0:
            rsame += 1
            rp -= 1

        ans += (lsame * rsame) # 중복 숫자 끼리 곱해줘야 그만큼의 갯수가 나온다.
    # if문을 나오면 해당 합의 중복이 제외된다.

    elif tmp < 0:
        lp += 1
    else:
        rp -= 1
print(ans)

✍️ 다른 사람 풀이

---

• 딕셔너리 풀이

🎈 참고

---