문제

U < V < W 또는 U > V > W일 때, 정수 V는 U와 W 사이에 있다.

비어 있지 않은 배열 A는 주어진 N개의 정수로 이뤄져 있는데, 숫자의 인덱스 (P, Q) 짝은 0 ≤ P < Q < N인 인접한 수가 A[P]와 A[Q] 사이에 없으며, A[P]≠A[Q]임을 나타낸다. 예를 들어, 배열 A에서는:

A[0] = 0
A[1] = 3
A[2] = 3
A[3] = 7
A[4] = 5
A[5] = 3
A[6] = 11
A[7] = 1

다음 인덱스 짝은 인접한 값을 갖고 있다.

(0,7), (1,4), (1,7), (2,4), (2,7), (3,4), (3,6), (4,5), (5,7)

예를 들어, 인덱스 4와 5는 인접한 값을 갖고 있는데, 왜냐하면 A[4] = 5와 A[5] = 3는 다르며, 배열 A에는 그 사이에 들어갈 값이 없다는 것이다. 즉, 숫자 4만이 사이에 들어갈 수 있으나 배열에 존재하지 않는다.

주어진 두 인덱스 P와 Q의 거리는 X ≥ 0에서는 abs(X) = X, X < 0에서는 abs(X) = -X일 때  abs(P-Q)로 정의된다. 예를 들어, 인덱스 4와 5 사이 거리는 1인데, 그 이유는 abs(4-5) = (5-4) = 1이기 때문이다.

함수를 작성하라:

class Solution { public int solution{int[] A); }

주어진 비어 있지 않은 배열 A는 N개의 정수로 이루어져 있으며, 인접한 값을 가진 배열의 가장 긴 거리를 반환한다. 이 함수는 인접한 인덱스가 없는 경우 -1을 반환해야 한다.

예를 들어, 주어진 배열 A는 다음과 같다:

A[0] = 1
A[1] = 4
A[2] = 7
A[3] = 3
A[4] = 3
A[5] = 5

이 함수는 다음 이유로 4를 반환해야 한다:

  • 인덱스 0과 4는 인접해있는데, 그 이유는 A[0] ≠ A[4]이며 배열이 A[0] = 1과 A[4] = 3 사이의 값을 갖고 있지 않기 때문이다.
  • 이들 인덱스의 거리는 abs(0-4) = 4이다.
  • 더 큰 수의 거리를 지닌 다른 인접한 인덱스 짝이 없다.

다음과 같이 가정한다:

  • N은 [1..40,000] 범위 내에 있다.
  • 배열 A의 각 요소는 정수이며, 범위 [-2,147,483,648..2,147,483,647] 내에 있다.

복잡도:

  • 기대되는 최악의 경우 시간 복잡도는 O(N*log(N))이다.
  • 기대되는 최악의 공간 복잡도는 O(N)이며 입력 공간 이후를 말한다 (입력 기호에 필요한 공간은 포함하지 않는다)

발상

  • 왼쪽부터 찾아서 그 값의 다음 인접한 수를 찾는 식으로 반복할까?
    • N개의 항목에 대해 반복하면서 N-1개의 반복을 다시 해야만 한다.
    • 더 좋은 방법이 있을 것이다.
  • 소트를 먼저 한 다음에 낮은 수부터 올라가면서 맞춰볼까?
    • 소트 알고리즘은 검증되어 있는 내부 라이브러리를 활용하면 더 좋을 것이다.
    • 같은 수를 건너뛰면 반복문이 한층 더 빠를 것이다.
    • 하지만 정렬하면 원래의 위치를 잃어버리잖아?
      • 원래의 위치는 왼쪽부터 차례로 원시적인 방법으로 찾으면 된다.
      • 찾는 순간 루프를 탈출하면 속도는 더욱 빠를 것이다.

풀이

import java.util.ArrayList;
import java.util.Arrays;

public class Question {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int[] A = new int[] {0,3,3,7,5,3,11,1};
		//int[] A = new int[] {1,4,7,3,3,5};
		//int[] A = new int[] {1,1,1,1,1,1,1,1};
		
		//랜덤한 40000개의 int를 넣는 부분
		int[] A = new int[40000];
		for(int i = 0; i < A.length; i++) {
			A[i]=(int)Math.round(Math.random()*2147483647*2-2147483647);
		}
		
		//시간 계산 시작
		long startTime = System.nanoTime();
		System.out.println("Result: "+solution(A));
		System.out.println("Elapsed Time: "+(System.nanoTime()-startTime)/1000000.0+"ms");
	}
	
	private static int indexOfArray(int[] A, int val, boolean reverse) {
		if(reverse) {
			//뒤에서 찾기
			for(int i = A.length-1; i >= 0; i--) {
				if(A[i]==val) {
					return i;
				}
			}
		} else {
			//앞에서 찾기
			for(int i = 0; i < A.length; i++) {
				if(A[i]==val) {
					return i;
				}
			}
		}
		return -1;
	}
	
	private static int findPairDistance(int[] A, int min, int max) {
		//왼쪽 오른쪽 각각 min, max 검색
		int aleft = indexOfArray(A,min,false);
		int aright = indexOfArray(A,min,true);
		int bleft = indexOfArray(A,max,false);
		int bright = indexOfArray(A,max,true);
		return Math.max(Math.abs(aleft-bright),Math.abs(aright-bleft));
	}
	
	public static int solution(int[] A) {
		//소트 후 중복 제거
		int[] sorted = A.clone();
		Arrays.sort(sorted);
		/*for(int i = 0; i < sorted.length; i++) {
			System.out.print(sorted[i]+",");
		}*/
		//ArrayList alSel = new ArrayList<>();
		int max = -1;
		for(int i = 1;i < sorted.length; i++) {
			//전항과 현재항의 차이
			int cha = sorted[i]-sorted[i-1];
			if(cha >= 1) { //차이가 1 이상이면 정수 변화로 보고 계산
				//alSel.add(sorted[i-1]);
				//findPairDistance(A,A[i-1],A[i]);
				max = Math.max(max, findPairDistance(A,sorted[i-1],sorted[i]));
				//두 값에 대한 좌우 검색 최대 거리를 구한 다음 max보다 클 때만 기록
				//System.out.println(String.format("값: (%d,%d), 거리: %d",sorted[i-1],sorted[i],findPairDistance(A,sorted[i-1],sorted[i])));
			}
		}
		
		
		return max;
	}

}