알고리즘/백준알고리즘

[백준] 7453번 합이 0인 네 정수

2021. 3. 23. 21:43
728x90
반응형

문제 설명

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

제한 사항

-첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

​-합이 0이 되는 쌍의 개수를 출력한다.

​

입출력 예

input

output

6

-45 22 42 -16

-41 -27 56 30

-36 53 -37 77

-36 30 -75 -46

26 -38 -10 62

-32 -54 -6 45

5

​

접근법

네 리스트의 조합을 한번에 다루면 for문이 4개나 생기기 때문에, 시간복잡도가 O(n4)가 되버려서 시간이 엄청 오래걸립니다. 따라서 리스트를 2개씩 쪼개서 계산하면 됩니다. 즉, a리스트와 b리스트의 계산을 먼저 하고 a+b의 합과 부호가 반대인 수가 c+d의 합에 있다면, 0이 되는 조건입니다. 여기서 a+b에 -2가 두가 있을때, c+d에 2가 있다면, 0이 되는 조합은 총 2개이겠죠? 따라서

중복을 고려해주셔야합니다!

이를 딕셔너리로 만들어서 key는 a+b, value는 개수로 넣어주시면 됩니다. 이렇게 만들어진 딕셔너리에 -(c+d)가 존재하면 그 value만큼 카운트해주시면됩니다.

​

코드 제출하실때 pyp3로 제출하셔야합니다! python3로 제출하면 계속 실패가 뜨더라구요 ㅠㅠ

찾아보니까 python으로 성공한사람이 없다고해요... 이분 탐색을 써도 python3에서는 계속 실패가 뜨네요

​

나의 코드

import sys

number = int(sys.stdin.readline())
a_list, b_list, c_list, d_list = [], [], [], []
for _ in range(number):
    a, b, c, d = map(int,sys.stdin.readline().split())
    a_list.append(a); b_list.append(b); c_list.append(c); d_list.append(d)

a_b_dict = dict()
for a in a_list:
    for b in b_list:
        a_b_dict[a+b] = a_b_dict.get(a+b, 0) + 1

count = 0
for c in c_list:
    for d in d_list:
        count += a_b_dict.get(-(c+d),0)

print(count)

 

반응형

'알고리즘 > 백준알고리즘' 카테고리의 다른 글

[백준] 1991번 트리 순회  (0) 2021.03.24
[백준] 1302번 베스트셀러  (0) 2021.03.23
[백준] 1431번 시리얼 번호  (0) 2021.03.22
[백준] 1449번 수리공 항승  (0) 2021.03.22
[백준] 2437번 저울  (0) 2021.03.21
'알고리즘/백준알고리즘' 카테고리의 다른 글
  • [백준] 1991번 트리 순회
  • [백준] 1302번 베스트셀러
  • [백준] 1431번 시리얼 번호
  • [백준] 1449번 수리공 항승
컴공누나
컴공누나
ML 엔지니어 컴공누나입니다:) wodbs9522@gmail.com
컴공누나의 지식 보관소ML 엔지니어 컴공누나입니다:) wodbs9522@gmail.com
컴공누나
컴공누나의 지식 보관소
컴공누나
전체
오늘
어제
  • 분류 전체보기 (267)
    • 컴공누나 소개 (2)
    • 언어 마스터 (4)
      • 파이썬 (4)
    • 알고리즘 (159)
      • 프로그래머스 (120)
      • 백준알고리즘 (39)
      • 알고리즘기초 (0)
    • 인공지능공부 (62)
      • 인공지능기본지식 (6)
      • LLM (3)
      • 인공지능기초수학 (9)
      • 프레임워크 (2)
      • 자연어처리 (16)
      • 컴퓨터비전 (2)
      • 그래프 (24)
      • Prolog (0)
    • 다른 분야 (4)
      • Docker (1)
      • Web (3)
    • 논문 (10)
      • 논문리딩 (6)
      • 게제논문 (4)
    • 꿀팁 (19)
      • 오류 정리 (8)
      • 소소한 팁 (11)

블로그 메뉴

  • 홈
  • 태그
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • 그래프
  • stanfordgnn
  • 자연어처리
  • 그래프신경망
  • transformer
  • 그래프강의
  • stanfordgraph
  • cs224w
  • GPT
  • 영상기반상식추론
  • 선형대수
  • GNN
  • 파이썬
  • 백준
  • nlp
  • Bert
  • 프로그래머스
  • selfattention
  • 스탠포드그래프
  • 선형대수기초

최근 댓글

최근 글

글쓰기 / 관리자
hELLO · Designed By 정상우.
컴공누나
[백준] 7453번 합이 0인 네 정수
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.