https://www.acmicpc.net/problem/7453
공부 날짜 : 2023.02.15
정답 참조 여부 : X
4개의 정수 리스트가 주어진다 각 리스트에서 하나의 수를 꺼내서 합했을 때 0이되는 경우의 수를 구하는 문제이다.
처음으로 떠올린 방법은 a와 b를 더하고, c와 d를 더해서 2개의 합리스트로 만들어준다.
그런다음 ab는 오름차순, cd는 내림차순으로 정렬해서 두개의 합이 양수이면 cd에서 다음 값을 꺼내고(cd는 내림차순이므로 다음 값이 더 작다 따라서 총 합이 작아짐), 음수이면 ab에서 다음 값을 꺼내는 방식으로 했다.(마찬가지로 ab는 오름차순이므로 총 합이 커짐) 그러다가 0이되면 결과를 +1 해준 뒤, 둘중 하나에서 다음 값을 꺼내오도록 했다.
첫번째 시도한 방법은 heap구조
ab는 최소힙, cd는 최대힙으로 구현하고자 했는데 시간초과가 났다. 힙에 넣고 빼는게 O(NlogN)이기 때문에 약 16억이 나와서 제한시간 12초이지만 시간초과가 나왔다.
다음으로 시도한 방법은 sort
원래 일반적으로 구현하는 sort는 O(N^2)이기 때문에 고려하지 않았지만, 파이썬에서 지원하는 sort는 (NlogN)이다.
파이썬의 정렬을 내가 구현할 자신이 없어서 시도 안했던 방법인데 일단 푸는게 중요해서 시도 해봤다.
또, 힙과 시간 복잡도가 같아 보이지만 2개의 힙에서 넣고 빼고 하기 때문에 *4를 sort는 2개의 리스트에서 하기 때문에 *2가 된다.에초에 빅오기법에서 둘다 무시하는 부분이지만 애매하게 차이가 나길래 시도 해봤다.)
결과는 틀렸습니다.
시간은 해결했지만 틀린이유가 같은 수가 중복이 되기 때문
-4 -4
4 4
에서 비교할 때 비교 순서가
0 0
0 1
1 1
이 되어서 단순히 다음 수를 가져오는 것 만으로는 만족할 수 없다.
그래서 같은 수의 개수를 세 줘야 하는데 방법이 잘 떠오르지 않았다.
그래서 사용한 방법은 딕셔너리
사실 제일 처음 떠오른 방법이 딕셔너리긴 한데 다른 언어에서는 딕셔너리 구조가 없어서 안하려 했다가 시도한 방법이 전부 안되서 결국 딕셔너리로 했다.
방법은 ab는 딕셔너리로 만드는데 a,b의 합을 key로 가지고 해당 값의 개수를 value로 가지는 딕셔너리로 만들었고, cd는 단순히 합 리스트로 만들었다.
그 다음 cd의 값을 ab에서 합이 0이되는 값이 있는지체크하여 그 개수만큼 answer에 더해 줬다.
소스코드
import sys
#import heapq
input = sys.stdin.readline
##################################################
n = int(input())
A = []
B = []
C = []
D = []
# 데이터를 입력받아 A,B,C,D에 저장
for _ in range(n):
a, b, c, d = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
D.append(d)
ab = {}
cd = []
#####################################################################
for i in range(n):
for j in range(n):
ab[A[i] + B[j]] = ab.get(A[i] + B[j], 0) + 1
cd.append(C[i] + D[j])
answer = 0
for i in cd:
answer += ab.get(-i, 0)
print(answer)