[Python] 백준, 7453(이진 탐색)

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

7453번: 합이 0인 네 정수

 

분명 이진 탐색이지만.. 이 글을 쓰는 지금도 시간 초과 때문에 이진 탐색을 적용할 엄두가 나질 않는다. 알고리즘 분류가 이진 탐색으로 되어 있지만 다른 방향으로 풀이하는 게 나은 문항들이 종종 보인다. 슬슬 다른 알고리즘 문항들도 풀어야 하나 보다.

 

풀이에 앞서 정리할 문법이 몇 가지 있다.

 

1) collections 모듈의 Counter

이건 전에도 언급은 한 적이 있지만 제대로 정리는 안 해놓은 것 같다.

from collections import Counter
test_list = ['a', 'a', 'b',' c', 'd', 'e', 'e', 'e', 'f', 'f', 'g']
counter = Counter(test_list)
counter['a']  #  결과값 2 출력
counter['b']  #  결과값 1 출력
counter['e']  #  결과값 3 출력

 

2) dict 매소드의 get(a, b) 함수

기본 문법이라 get은 알고 있었는데, b의 역할은 몰랐다.

dict에서 a값을 가져오며, 이때 a가 존재하지 않으면 b값을 return 한다.

 

 

3) collections모듈의 defaultdict

dict의 확장판 같은 건데, 없는 key값을 요청해도 keyError가 발생하지 않는다.

from collections import defaultdict
 
dic_int = defaultdict(int)
dic_int[1]  #  0을 return하고, dic_int = {1: 0}
dic_int[2] = 'a'  #  dic_int = {1: 0, 2: 'a'}
 
dic_list = defaultdict(list)
dic_list['key']  #  []를 return하고, dic_list = {'key': []}
dic_list['a'] = 4  #  dic_list = {'key': [], 'a': 4}
 

 

#PYTHON CODE (1) - 1차 시도

import sys
 
n = int(sys.stdin.readline())
a_list, b_list, c_list, d_list = [], [], [], []
 
for i in range(n):
    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)
 
list1, list2 = [], []
 
for i in a_list:
    for j in b_list:
        list1.append(i + j)
 
for k in c_list:
    for u in d_list:
        list2.append(k + u)
 
list1.sort()
list2.sort()
 
answer = 0
 
for i in list1:
    pl, pr = 0, len(list1) - 1
    while pl <= pr:
        pc = (pl + pr) // 2
 
        if list2[pc] == -i:
            if list2[pc] == list2[pc + 1]:
                answer += 1
            answer += 1
            break
 
        elif i + list2[pc] >= 0:
            pr = pc - 1
 
        else:
            pl = pc + 1
 
print(answer)

import sys
from collections import Counter
 
n = int(sys.stdin.readline())
temp = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
 
a, b, c, d = zip(*temp)
 
list1, list2 = [], []
 
for i in range(len(a)):
    for j in range(len(a)):
        list1.append(a[i] + b[j])
        list2.append(c[i] + d[j])
 
answer = 0
counter = Counter(list2)
 
for num in list1:
    answer += couter[-num]
 
print(answer)

# PYTHON CODE (3) 

from sys import stdin
from collections import defaultdict
 
read = stdin.readline
n = int(read())
 
A, B, C, D = [], [], [], []
 
dic1 = {}
dic2 = {}
 
for _ in range(n):
    a, b, c, d = map(int, read().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
 
result = 0
 
for a in A:
    for b in B:
        dic1[a + b] = dic1.get(a + b, 0) + 1
 
for c in C:
    for d in D:
        result += dic1.get(-(c + d), 0)
print(result)

 

맞긴 했지만 이진 탐색도 들어가지 않았을뿐더러, 혼자 힘으로 푼 것도 아니라 상당히 찜찜하다. 갈길이 너무 멀다.