Replies: 1 comment 3 replies
-
|
간만입니다 주성님 혹시 시간나실때 이거 한번 풀어보시겠어요? |
Beta Was this translation helpful? Give feedback.
3 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
-
문제 : https://www.acmicpc.net/problem/15970
아이디어
색깔이 같은 점들 중 가장 가까운 점끼리의 거리를 구해야 하니까 일단 색깔별로 ArrayList에 분류한 후 정렬해준다.

정렬의 특성을 생각해보면 정렬 후 각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다는 것을 알 수 있다. 따라서 가장 가까운 점끼리의 거리를 구해야 하므로 기준 점의 왼쪽, 오른쪽 점까지의 거리를 비교해서 가장 가까운 점을 찾아낼 수 있다.
시간복잡도
색깔별로 정렬할 때 시간 복잡도가 O(N log N)이고, 가까운 점을 찾을 때 시간 복잡도가 O(N)이다.
N의 최댓값은 5000이므로 1초안에 가능한 풀이이다.
구현
Beta Was this translation helpful? Give feedback.
All reactions