좌표들이 주어질때 좌표간 간격이 될 수 있는 모든 수를 찾는 방법

30105번: 아즈버의 이빨 자국 (acmicpc.net)

 

초코바에 이빨 자국을 남기는데 이빨간 간격이 k라고 한다면 0이상의 수 x에 대하여 x부터 x+k에 이빨 자국을 남긴다

 

이빨자국을 동일한 위치에 여러번 남겨도 한번만 보인다

 

이빨자국이 남겨진 좌표들 x0,x1,x2,...,xn이 주어진다면 가능한 k를 모두 구해본다면?

 

 

1. 무식하게 찾는 방법

 

쉽게 생각할 수 있는 방법은.. 일단 모든 좌표쌍 (xi,xj)에 대하여 간격 k = xj - xi를 구하고

 

간격 k에 대응하는 xi,xj를 저장해둔다

 

모든 간격 k에 대하여 간격 k에 대응하는 x좌표가 주어진 이빨 자국 수와 같다면 해당 간격 k는 가능한 k라는 것

 

예를 들어 [0,5,10,15]로 주어질때

 

모든 쌍에 대하여 5-0 = 5이므로 h[5] = [0,5], 10-0 = 10이므로 h[10] = [0,10],...

 

10-5  = 5이므로 h[5] = [0,5,10], ... 15-10 = 5이므로 h[5] = [0,5,10,15]이므로...

 

k = 5는 가능한 k이다.

 

마찬가지로 15 - 5 = 10이므로 h[10] = [0,10,5,15]이므로 역시 k = 10도 가능한 k이다.

 

하지만 15 - 0 = 15에서 h[15] = [0,15]만 존재하므로 k = 15는 불가능한 k이다.

 

n = int(input())

A = list(map(int,input().split()))

h = {}

for i in range(n-1):
    
    for j in range(i+1,n):
        
        k = A[j] - A[i]

        if h.get(k,0) == 0:
            
            h[k] = set()

        h[k].add(i)
        h[k].add(j)
            
answer = []

for k in h:
    
    if len(h[k]) == n:
        
        answer.append(k)

answer.sort()

print(len(answer))
print(*answer)

 

 

 

2. 조금 더 똑똑하게 찾는 방법

 

브루트포스의 백미는 탐색 범위를 줄이는데 있다

 

위에서 가능한 간격 k를 모든 (xi,xj)에 대해 조사했지만 (x0,xi)에 대해서만 조사한다면...

 

k = xi - x0에 대하여 0번과 i번을 물었으니 j = 1번부터 조사해서 xj, xj+k = xj, xj+(xi-x0)에도 물 수 있는지 조사하면 된다

 

즉 X값들을 미리 hash에 저장해두고 i = 0,1,2,...에 대하여 k = xi - x0로 해두고

 

j = 1,2,...에 대하여 xj + (xi-x0) = xj + k가 hash에 존재하는지만 확인하면 충분하다

 

#x0,x1,..,xn이 주어지고 k > 0 , xi,xi+k에 좌표를 남겼을때 가능한 k를 모두 찾는 방법
n = int(input())

A = list(map(int,input().split()))

#X값들을 미리 저장해두고
h = {}

for i in range(n):
    
    h[A[i]] = 1

answer = []

#i = 1,2,..,n-1에 대해 k = xi - x0에 대하여 x0,xi에 좌표를 남겼다면
#j = 1,2,..,n-1에 대해 xj,xj+k에 좌표를 모두 남길 수 있다면 충분하다
for i in range(1,n):
            
    k = A[i] - A[0]
    
    no = False

    for j in range(1,n):
        
        #[xj,xj+k]가 존재하면 상관없긴한데, 존재하지 않는다면
        if h.get(A[j] + k,0) == 0:
            
            #[xj-k,xj]가 존재한다면 조건을 만족하게 된다
            #이걸 확인하지 않으면
            #[0,5,10,15]의 경우 k = 5에서 [0,5], [5,10], [10,15]까지 보다가
            #[15,20]이 존재하지 않으니 k = 5는 불가능하다!라고 결론내린다
            #[10,15]가 존재하니 k = 5가 가능하다라고 할려면 xj-k를 봐야함
            if h.get(A[j] - k,0) == 0:
                
                no = True
                break
    
    if no == False:
        
        answer.append(k)

print(len(answer))
print(*answer)

 

 

여기서 주의할 점은 xj에 대하여 xj+k가 존재하는지 확인하면 된다고 했지만

 

xj+k가 존재하지 않더라도 xj-k가 존재한다면 xj-k, xj로 조건을 만족하기 때문에 상관없다

 

예를 들어 [0,5,10,15]일때 k = 5-0에 대하여 [0,5], [5,10],[10,15]까지는 무리없이 가다가

 

xj = 15일때 xj+k = 20이 존재하지 않으니까 조건을 만족하지 않는다? 하면 안되잖아

 

xj = 15일때 xj-k = 10이 존재하여서 [10,15]가 존재하니까 조건을 만족하게 된다