[Seop's의 코드풀이] 백준 7453 합이 0인 네 정수 - Python

이번에 풀어볼 문제는 백준 7453번인 합이 0인 네 정수라는 문제입니다.

문제는 다음과 같습니다.

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

7453번: 합이 0인 네 정수

 

문제를 살펴보면 4개의 배열이 있고 각 배열의 원소를 하나씩 적출해내어 합을 0으로 만들면 되는 문제입니다.

 

필자는 처음 시도할때 조합을 이용하여 풀고자 했습니다. 

itertools 의 product 을 활용하면 각각의 배열에 있는 원소들을 하나씩 선택에서 조합으로 반환합니다.

정답은 맞을 수 있겠지만 메모리 초과가 나오게 됩니다.

 

메모리가 초과되니 각각 하나씩 다 더해보는 과정을 진행하게 되면 시간초과가 발생하게 됩니다.

 

최대한 공간복잡도와 시간복잡도를 줄여보고자 다음과 같은 방법을 시도했습니다.

1. ABCD 4개의 배열중 2개를 선택하여 합의 값을 알아낸다.(필자는 A,B를 선택)

2. 1에서 알아낸 값을 dict에 저장한다. key : 합의 값, Value : 나온 횟수 (추후 시간복잡도를 줄이기 위해)

3. 1에서 선택한 배열 이외의 나머지 2개 배열에 대해서 합의 값을 알아낸다.

4. 3에서 구한 값이 dict에 있다면 정답에 해당 value 값을 더한다.

 

4개의 배열을 두개씩 나눔으로서 시간복잡도를 N^4 에서 2N^2로 줄였고 dict를 활용해 탐색하는데 시간을 줄였다.

전체적인 코드는 다음과 같습니다. 또한 기존에 itertools 를 활용한 코드는 다음 링크에 있습니다.

github.com/miseop25/Back_Jun_Code_Study/tree/master/back_joon/자료구조/back_joon_7453_합이0인네정수

miseop25/Back_Jun_Code_Study

 

import sys
input = sys.stdin.readline

def soluction(N) :
    answer = 0
    A = []
    B = []
    C = []
    D = []
    for _ in range(N) :
        a1,b1,c1,d1 = map(int, input().split(" "))
        A.append(a1)
        B.append(b1)
        C.append(c1)
        D.append(d1)

    case1 = dict()
    for i in range(N) :
        for j in range(N) :
            temp = A[i] + B[j]
            if temp in case1 :
                case1[temp] += 1
            else :
                case1[temp] = 1
    for i in range(N) :
        for j in range(N) :
            temp = -(C[i] + D[j])
            if temp in case1 :
                answer += case1[temp]

    return answer

if __name__ == "__main__":
    n = int(input())
    print(soluction(n))