[BOJ] 2143 두 배열의 합 - python

2143번: 두 배열의 합

2143번: 두 배열의 합

풀이

처음에는 아무것도 없으면 0 출력 하라는 말에 다 해보는 문제인줄 알았다. A,B가 1000개밖에 없어서 다 해도 될 줄.. 근데 아니나다를까 시간초과 → 부분합 사용했는데도 왜 시간초과지,,하고 측정했는데 세상에 7초 떴당 부분합이 어디서부터 어디까지인지를 기억할 필요는 없다 → dictionary사용 list합은 sum으로 사용 가능 aList의 부분합을 구한 후 bList도 구하고 싶겠지만 그렇게 하면 시간초과가 나기 때문에, bList for문 돌릴 때는 바로 조건 검사해서 answer에 더하기 aList에서 각 부분합의 개수를 value에 넣어놓았으므로, bList에서 조건 검사할 때 a+b=T ⇒ a = T-b인 value값을 바로 answer에 더한다. (생각지도 못했다.. Wow)

시간초과 코드

import sys
import math
import time
start = time.time()

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

T = int(input())
N = int(input())
aList = list(map(int,input().split(" ")))
M = int(input())
bList = list(map(int,input().split(" ")))
#print(T,N,aList,M,bList)

# 음수도 가능하고, 리스트 안에 있는 수들 소팅한 것을 보는게 아니라, 순서대로 보는 것임
# 가능한 경우가 한 가지도 없을 경우에는 0을 출력 -> 다 해보는 거다!
# 부분합을 다 더해놓고 부분합으로 조합
# 0 0-1 0-2 0-3 0-4
# 1-3 2-4 / 1-3 2-4

# 부분합 구하기
pSumA,pSumB = [0 for _ in range(N)], [0 for _ in range(M)]
pSumA[0],pSumB[0] = aList[0], bList[0]
for n in range(1,N):
    pSumA[n] = pSumA[n-1] + aList[n]
for m in range(1,M):
    pSumB[m] = pSumB[m-1] + bList[m]
#print(pSumA,pSumB)

answer = 0
# 부분합으로 조합하기
for a in range(N):
    for b in range(a,N):
        if a == b:
            tmpA = aList[a]
        elif a == 0:
            tmpA = pSumA[b]
        else:
            tmpA = pSumA[b] - pSumA[a-1]

        for aa in range(M):
            for bb in range(aa,M):
                if aa == bb:
                    tmpB = bList[aa]
                elif aa == 0:
                    tmpB = pSumB[bb]
                else:
                    tmpB = pSumB[bb] - pSumB[aa - 1]

                if tmpA + tmpB == T:
                    answer += 1

print(answer)

end = time.time()
print(f"{end - start:.5f} sec") #6.7초..어마무시..

최종 코드

import sys
from _collections import defaultdict

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

T = int(input())
N = int(input())
aList = list(map(int,input().split(" ")))
M = int(input())
bList = list(map(int,input().split(" ")))

#부분합이 같은거를 몇 번 사용해도 뭐 사용했는지는 관심 없음 -> dict 사용하기
aDict = defaultdict(int)
for a in range(N):
    for aa in range(a,N):
        aDict[sum(aList[a:aa+1])] += 1

answer = 0
for b in range(M):
    for bb in range(b,M):
        answer += aDict[T - sum(bList[b:bb+1])]

print(answer)

얻어가는 것

• 시간 측정
• import math import time start = time.time() #어쩌구저쩌구 end = time.time() print(f"{end - start:.5f} sec")
• defaultdict

  from _collections import defaultdict
  
  intDict = defaultdict(int) #{'key1' : 0}
  listDict = defaultdict(list) #{'key1' : []}
  setDict = defaultdict(set) #{'key1' : set()}
  

  intDict = defaultdict(int)
  
  for a in range(N):
  	intDict[어쩌구[a]] += 1
  
  #dictionary의 초기값을 검사할 필요 없다.
  

  https://dongdongfather.tistory.com/69
• : 키가 존재하지 않을 때 if조건을 검사하는 과정을 생략할 수 있다.

느낀점

"211130"

소요 시간 : 1h

• defaultdict라는 아이를 알게되어 매우 뿌듯한 시간이었다 짱짱! 이제 많이 애용해야지
• 아직 코딩테스트는 갈 길이 멀다