[백준 - Python] 7453 - 합이 0인 네 정수

0.  문제 링크

 

 

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

7453번: 합이 0인 네 정수

---

1.  풀이 방법

 

 

일단 내가 푼 방식을 먼저 얘기하고 Two Pointer로 풀 수 있는 방법에 대해 얘기해 보자.

나는 일단 정렬 이런 거 안 했다.

a, b, c, d가 있으니 a와 b를 합쳐서 ab, c와 d를 합쳐서 cd로 만들었다.

이때 cd를 Counter 객체로 만들었다.

Counter 객체는 파이썬 내장 모듈이므로 한 번 찾아보면 될 것 같다.

아무튼 ab에 있는 애들 하나씩 꺼내서 cd에 그에 해당하는 음수가 있다면 이는 0이 되는 것이 아닐까?

참고로 cd에는 특정 숫자가 몇 개 있는지 저장되어 있으므로, 음수로 참조하고 그 개수를 cnt에 더하면 된다.

 

 

두 번째 Two Pointer 방법은 간단하다.

ab와 cd를 만들고 둘 다 정렬한다.

그리고 포인터는 ab의 0번째에, cd의 마지막에 놓는다.

당연히 이때는 ab에 있는 포인터는 음수(혹은 가장 작은 수)를 가리킬 것이고, cd에 있는 포인터는 양수를 가리킬 것이다.

포인터가 가리키는 값들을 더해서 양수가 나온다면, cd에 있는 포인터를 왼쪽으로 한 칸 옮기고,

만약 음수가 나온다면, ab에 있는 포인터를 오른쪽으로 한 칸 옮기면 된다.

만약 두 개를 더했는데 0이 나오면 cnt를 1 더하고, 포인터를 각각 좌우로 한 칸씩 당기면 된다.

---

2.  코드

 

 

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

if __name__ == "__main__":
    n = int(input())
    a, b, c, d = [], [], [], []
    for _ in range(n):
        t1, t2, t3, t4 = map(int, input().split())
        a.append(t1)
        b.append(t2)
        c.append(t3)
        d.append(t4)

    ab, cd = [i + j for i in a for j in b], [i + j for i in c for j in d]

    cnt = 0
    cd = Counter(cd)
    for i in ab:
        cnt += cd[-i]
    print(cnt)

---

3.  마무리