Problem | 백준 15970번 화살표 그리기
직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다.
각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다.
각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.
모든 점에 대해서 같은 색깔을 가진 다른 점이 항상 존재한다. 따라서 각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표를 항상 그릴 수 있다.
예를 들어, 점들을 순서쌍 (위치, 색깔) 로 표시할 때, a = (0,1), b = (1, 2), c = (3, 1), d = (4, 2), e = (5, 1)라고 하자.
아래 <그림 2>에서 이 점들을 표시한다. 여기서 흰색은 1, 검은색은 2에 해당된다.
- 입력 : 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어 진다. 다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.
점들이 가진 각 색깔 c에 대해서, 색깔 c를 가진 점은 정확히 두 개 존재하고 점들의 개수는 2 ≤ N ≤ 10를 만족한다.
- 서브태스크 :
1) 점들의 색깔은 모두 동일하고 점들의 개수는 2 ≤ N ≤ 300를 만족한다.
2) 점들의 색깔은 정확히 두 가지이고 점들의 개수는 2 ≤ N ≤ 1,000를 만족한다.
1) 점들의 개수는 2 ≤ N ≤ 5,000를 만족한다.
💡 가장 쉽게 생각 할 수 있는 방법 고민
만약 A라는 배열에 회색을 기준으로 한다면 A[i]와 A[j]를 고민하고
min값을 계속 temp 변수를 통해 교체해주어 최단 거리를 찾는다.
가능하지만, O(n^2) 으로 시간 초과가 날 가능성이 존재한다.
📌 정렬 사용해서 풀이하기
같은 색깔들의 점만 모아본다.
* 정렬하면 인접한 것이 자신의 양 옆에 위치한다는 속성을 이용 *
양 옆 숫자 중 차이가 적은 값을 화살표 값으로 추가한다.
1. 같은 색상의 점들로 모으기
ArrayList<Integer>[] a=new ArrayList[N+1];
for(int color=1;color<=N;color++)
a[color]=new ArrayList<Integer>();ArrayList 배열 값을N+1으로 한 까닭은 0은 Null 값이라 생각하고 1 ~ N 자리를 마련해 두는 것이다.
다음은 a[color]에 맞는 위치들이 ArrayList형태로 add될 것이다.
2. 위치에 맞는 색상 add
for(int i=0;i<N;i++) {
coor=sc.nextInt();
color=sc.nextInt();
a[color].add(coor);
}
