[백준] 30105 - 아즈버의 이빨 자국 (G5)

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

30105번: 아즈버의 이빨 자국

처음 문제를 읽었을 때는 감이 안왔는데, 시간 제한을 보고 브루트포스라는 감을 잡아 풀었다.

N의 사이즈가 4000개이므로, 임의 2개의 점 사이 모든 간격을 구하는데 1.6 * 10^7 의 연산이 필요하고, 이는 3초안에 충분히 가능한 연산이다.

 

나는 임의 두점 x1, x2 사이의 거리를 구하고, 해시맵에 그 거리를 key 로 하여 그 거리를 구성한 점들을 set으로 저장했다.

 

Map[distance] = {x1, x2}

 

이런 형태가 될 것이다.

이미 집합이 존재하는지 체크하기 위해 try - except 문으로 len(Map[distance]) 를 수행시키고, 에러가 발생하면 아직 distance 키가 존재하지 않으므로 해당 키에 set을 새로 생성하고나서 값을 추가해주었다.

 

맵에서 특정 키가 존재하는지 체크할 때, O(n) 시간으로 하나하나 도는 것보다 에러 처리로 푸는 경우가 더 많다.

(다른 더 좋은 방법이 있다면 알려주세요..)

 

이렇게 추가를 하고나서 집합의 사이즈를 측정했을 때, 모든 점이 다 들어있다면 이 distance는 가능한 distance 인 것으로 보고 체크해주면 끝이다.

 

n = int(input())
positions = [*map(int, input().split())]
check = dict()
ans = []
for i in range(n):
    for j in range(i+1, n):
        diff = positions[j] - positions[i]
        try:
            len(check[diff])
        except:
            check[diff] = set()
        finally:
            check[diff].add(positions[j])
            check[diff].add(positions[i])
            if len(check[diff]) == n:
                ans.append(diff)

print(len(ans))
print(*sorted(ans))

말로 길게 설명했지만, 코드만 읽어도 직관적으로 이해할 수 있을 것이라고 생각한다.