BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/2143
2143번: 두 배열의 합
첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그
www.acmicpc.net
내가 작성한 코드
import sys
from collections import defaultdict
from collections import deque
read = sys.stdin.readline
def read_data():
T = int(read().rstrip())
len_A = int(read().rstrip())
A = list(map(int, read().rstrip().split()))
len_B = int(read().rstrip())
B = list(map(int, read().rstrip().split()))
return T, A, len_A, B, len_B
def make_accu(A):
accu_A = [A[0]]
for i in range(1, len(A)):
accu_A.append(accu_A[-1] + A[i])
return accu_A
def get_all_partial_sum(accu_A):
count_A = defaultdict(lambda: 0)
for e_i, e in enumerate(accu_A):
count_A[e] += 1
for s_i in range(e_i):
s = accu_A[s_i]
count_A[e - s] += 1
return count_A
T, A, len_A, B, len_B = read_data()
accu_A = make_accu(A)
accu_B = make_accu(B)
count_B = get_all_partial_sum(accu_B)
answer = 0
for a_i, a in enumerate(accu_A):
answer += count_B[T - a]
for s_i in range(a_i):
s = accu_A[s_i]
answer += count_B[T - (a - s)]
print(answer)
- 누적합 배열(make_accu)
- 누적된 배열의 합을 나타내는 배열 만들기
- 부분배열의 합(get_all_partial_sum)
- 누적합을 이용하여 부분배열이 만들 수 있는 모든 합을 해쉬로 저장
- 해쉬 사용
- 한 배열에 대한 부분배열의 합 - 목표값의 해쉬를 모두 더하여 출력
다른 사람이 작성한 코드
import sys
from _collections import defaultdict
T = int(sys.stdin.readline())
a = int(sys.stdin.readline())
listA = list(map(int, sys.stdin.readline().split()))
b = int(sys.stdin.readline())
listB = list(map(int, sys.stdin.readline().split()))
dictA = defaultdict(int)
ans = 0
for i in range(a):
for j in range(i, a, 1):
dictA[sum(listA[i:j+1])] += 1
for i in range(b):
for j in range(i, b, 1):
ans += dictA[T - sum(listB[i:j+1])]
print(ans)
- sum을 사용
- 누적합 -> 해쉬를 sum -> 해쉬로 바로 적용하여 간략하게 작성
[알고리즘][python][백준 2143]두 배열의 합
백준 2143문제풀이입니다.
velog.io
기억해야할 것
- 메모리 초과
- 처음에 두 배열 모두 해쉬로 만들어 메모리 초과
- 한 배열만 해쉬로 작성하여 통과
'코딩테스트' 카테고리의 다른 글
[백준][BFS] MooTube (Silver) (0) | 2022.02.08 |
---|---|
[백준][구현] 치킨 배달 (0) | 2022.02.08 |
[프로그래머스][위클리챌린지] 8주차 - ? (0) | 2021.09.27 |
[프로그래머스][KAKAO_인턴][2019] 징검다리 건너기 (0) | 2021.09.08 |
[프로그래머스][KAKAO_인턴][2019] 호텔 방 배정 (0) | 2021.09.08 |