[Python] 백준 7453

 

세상 복잡하고 까다로웠다..

 

 

 

 

이것 저것 시도해보았는데 12초나 주어진 시간이 자꾸 초과돼서 이틀이나 걸린 문제,,

비슷한 유형의 문제가 많다. 백준 1208번 문제도 같은 유형이므로 유형에 대한 설명은 아래 링크에서 참조

 

📌https://990427.tistory.com/48

[Python] 백준 1208

 

우선 1208번과 같이 딕셔너리를 사용해서 문제를 풀었더니 시간초과가 났다.

이유는 정말 모르겠다... 딕셔너리의 시간복잡도가 O(1)이긴 하지만 숨어있는 상수가 매우 크다고 한다.

 

 

실패했지만 오류는 없다고 생각하는 코드

import sys
from collections import defaultdict

n=int(sys.stdin.readline())
A,B,C,D=[],[],[],[]
for i in range(n):
    a,b,c,d=map(int, sys.stdin.readline().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

ab=defaultdict(int)
cd=defaultdict(int)
for i in range(n):
    for j in range(n):
        ab[A[i]+B[j]]+=1
        cd[C[i]+D[j]]+=1

res=0
for i in ab.keys():
    if cd[-i]:
        res+=(ab[i]*cd[-i])
print(res)

 

어쨌든 위 코드로 백준에서는 시간초과가 계속해서 나기 때문에 다른 방법을 찾아야 한다.

Python3으로는 통과한 사람이 없고 Pypy3로 통과한 사람들의 코드를 보았다.

딕셔너리를 사용하지 않고 while문으로 two-pointer를 사용하였다.

1208번에 중복되는 부분에 대한 검사가 귀찮아서 딕셔너리를 사용했었는데 결국 귀찮은 구현을 하게 되었다...

 

 

간신히 통과한 코드

import sys

n=int(sys.stdin.readline())
A,B,C,D=[],[],[],[]
for i in range(n):
    a,b,c,d=map(int, sys.stdin.readline().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.append(A[i]+B[j])
        cd.append(C[i]+D[j])

ab.sort()
cd.sort()
res=0
l=0
r=len(cd)-1
while l<len(ab) and r>=0:
    if ab[l]+cd[r]>0:
        r-=1
    elif ab[l]+cd[r]<0:
        l+=1
    else:
        a=1
        b=1
        while l<len(ab)-1 and ab[l+1]==ab[l]:
            l+=1
            a+=1
        while r>0 and cd[r-1]==cd[r]:
            r-=1
            b+=1
        res+=(a*b)
        l+=1
        r-=1

print(res)

 

배열에서 같은 숫자가 몇개인지 while문을 통해 검사한 후 결과를 추가해주는 방식이다.

 

 

.

.

.

.

.

 

 

삽질의 흔적