[BOJ] 7453 합이 0인 정수 - python

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

7453번: 합이 0인 네 정수

풀이

list를 이용하면 시간 초과가 난다. 왜 그런지는 모르겠음... if문 검사하는 것도 시간이 많이 걸리나..? 몇번째 애를 가지고 했는지는 중요하지 않고, 그냥 걔가 몇 번 쓰였는지만 중요한 문제라면 dictionary를 사용하자. O(n^4)의 시간복잡도로는 딱 봐도 풀 수 없는 문제이므로 AB,CD를 나누어 생각한다. AB를 더해서 dict에 넣어 놓는다. 이 때 값이 존재하는지 검사하는 것 조차 시간이 많이 드니까 dict.get(값,default) 를 사용해서 dict AB를 세팅한다. 이후 CD를 또 dict로 만든 후 경우의 수를 구해도 좋겠지만 시간을 조금이라도 아끼기 위해 c+d하면서 동시에 AB에 절댓값만 다른 아이가 존재하는지 검사한다. 얘도 dict.get을 사용한다.

최종 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

N = int(input())
A,B,C,D = [],[],[],[]

for n in range(N):
    a,b,c,d = map(int,input().split(" "))
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

AB = {}
for a in A:
    for b in B:
				#dictionary에 이미 존재하면 그 값을, 존재하지 않으면 default값으로 0을
        AB[a+b] = AB.get(a+b,0) + 1 
  
answer = 0
for c in C:
    for d in D:
        answer += AB.get(-(c+d),0)
print(answer)

얻어가는 것

• dict의 default값

  AB = {}
  #AB[ab]값이 존재하면 그 값을, 존재하지 않으면 디폴트값을 return한다.
  AB.get(ab,디폴트값)
  
  #ex) 검사 후 저장하기
  AB[a+b] = AB.get(a+b,0) + 1 
  #ex) 있으면 가져오고 아니면 0 가져오기
  answer += AB.get(-(c+d),0)
  ​

느낀점

"211202"

소요 시간 : 1h

• 시간이 12초이길래 빡센 문제일거라고는 생각했는데 왜 똑같은 방법인데 시간초과 내는건데,,
• 그래도 쪼개서 하고, -절댓값으로 하는 아이디어는 잘 냈다.
• for문을 다 수행하고 나서 또 수행하는 경우에는 한 번 수행하고 거기서 조건 검사를 끝낼 수 있는지 확인하자
• 몇 번째 애를 사용했는지는 중요하지 않고, 그냥 걔를 몇 번 사용했는지만 중요한 애라면 dict를 통해서 빈도를 저장해놓아서 사용하는 방법을 생각해보자(dict.get애용하기! → defaultdict도 좋은데 느리다고 함)