boj 7453 합이 0인 네 정수 (골드2)

요즘 bfs나 삼성문제만 계속 풀다가 오랜만에 다른 문제를 풀어봤다

단순하게 다 4중 for문을 돌린다고 생각하면 인풋이 4000개까지 가능하기에
O(n^4)로는 통과가 불가능하다

내 풀이

import sys
input = sys.stdin.readline

n = int(input())

aa = []
bb = []
cc = []
dd = []
answer = 0

for i in range(n):
  a,b,c,d = map(int,input().split())
  aa.append(a)
  bb.append(b)
  cc.append(c)
  dd.append(d)

dic_a = {}

for i in aa:
  for j in bb:
    if i + j in dic_a:
      dic_a[i+j] += 1

    else :
      dic_a[i+j] = 1

for i in cc:
  for j in dd:
    if -(i+j) in dic_a:
        answer += dic_a[-(i+j)]
  
print(answer)

N^4의 시간복잡도를 줄이기 위해 N^2짜리 2개로 나눠서 dict를 통해 비교해주는것이 아이디어이다.
단순히 합이 0인지만 체크하면 되기에 소스 자체는 엄청 간단하다.

하지만 N^2으로 낮춰도 파이썬 자체가 느려서 통과가 간당간당하다.
원래 처음에는 dict을 2개 만들어서 A,B 배열 C,D 배열을 각각 처리해주고, 두개의 dict를 비교하며 풀었는데, 그러면 무조건 시간초과가 난다.
생각해보니 값만 비교하면 되기에 2번째 dict는 구지 만들어서 데이터를 저장해둘 필요가 없어서 한개로 줄였더니 겨우 통과되었다. 그나마도 pypy에서만 되는것 같다.

결과

시간초과 안나게 할 수 있는지 연구하느라 정말 많이 돌려봤다.
어떻게 해야 통과될까 싶어서 구글링하면서 다른분들이 올려둔 코드도 돌려봤는데 파이썬으로 통과되는건 없는것같다.. 심지어 pypy에서도 같은코드로 돌렸는데 시간초과 나기도하고 통과되기도 한다.
이럴땐 역시 c++이 ..

새로 공부한것

다른분들 코드를 찾아보다가 defaultdict에 대해서 알게되었다.
그래도 파이썬으로 코테문제를 꽤나 풀어봤다고 생각하는데 완전 처음보는거라 뭔지 찾아봤다.
딕셔너리의 기본값을 미리 설정해둘수 있는 기능이다
from collections import defaultdict 해줘야 한다

기본 dict 사용시

dic_a = {}

for i in aa:
  for j in bb:
    if i + j in dic_a:
      dic_a[i+j] += 1

    else :
      dic_a[i+j] = 1

defaultdict 사용시

dic_a = defaultdict(int)

for i in aa:
  for j in bb:
  	dic_a[i+j] += 1

defaultdict() 하고 괄호안에 str, int, list 등 자료형을 넣어주면
해당 자료형의 기본형으로 초기화가 된다.

그래서 카운트를 해야할 상황에서 위에처럼 특정 원소가 dict 안에 존재하는지 if 문을 나누어서 처리할 필요없이 그냥 +=1 처리만 해주면 되기에 코드가 조금더 짧아진다.

하지만 성능적으로 속도가 더 빨라진다거나 하는것 같지는 않아서 막 써야할 필요는 못느끼겠다.
카운팅하는 상황에서 코드를 조금 더 간결하게 하는 용으로 쓰일것같다.

끝!