문제 조건

아래와 같은 랜덤한 숫자 목록 중 특정 조건의 패턴 찾기.
1 2 4 6 4 6 7 8 2 1 2 5 4 7 2 8 9 0 8 2 7 0 6 4 2 3

특정 제공된 숫자 7 8 2 의 변경된 조건을 찾을때

  • 원본 7 8 2 를 찾을때
  • 원본의 순서가 변경된 조건을 찾을때 8 7 2 또는 8 2 7, 2 7 8 등
  • 원본의 값의 위상이 동일한 수준으로 변경될때, 모두 +1한 경우 8 9 3, -2한 경우 5 6 0과 같은 경우
  • 순서와 위상이 동시에 적용된 경우

위 조건의 패턴이 몇번 있는지를 찾을 때.

접근 방법

  1. 제공된 값을 배열화 한다.
    arr = [1, 7, 4, 6, 4, 6, 7, 8, 2, 1, 2, 5, 4, 7, 2, 8, 9, 0, 8, 2, 7, 0, 6, 4, 2, 3]

  2. 찾을 7 8 2의 길이를 제외한 만큼 for문으로 순회한다. 
     int len = 3; // `7 8 2` 의 길이
 int count = 0; // 패턴수
 for (i = 0; i <= arr.length - len ; i++) {
     count += Search(i);
 }

 int Search(int start){
     // arr의 i 위치에서 len 만큼을 복사
      1, 7, 4
      	7, 4, 6
            4, 6, 4

     int[] asort = new int[len];
     System.arraycopy(arr,start,asort,0,len);
     Arrays.sort(asort);
     // arr 의 갯수를 복사하고, 오름차순 정렬 `1, 7, 4` -> `1, 4, 7`
     // 비고 대상도 복사하여, 오름 차순 정렬  `7 8 2` -> `2 7 8`

     // 위상을 조정함
     // `1, 7, 4` -> `1, 4, 7` -> `0, 3, 6` 최소값 1을 0기준의 위상으로 조정, 모두 -1을 진행
     // `7 8 2` -> `2 7 8` -> `0 5 6` 최소값 2를 기준으로 0으로 이동, 모두 -2를 진행

     // 위상 이동까지 완료하여 비교를 진행함.
 }
  3. 비교할 값을 정렬하고, 비교할 범위의 최소값을 0 기준으로 위상을 조정한다. 7 8 2 에 순서는 오름차순 정렬에 의해서 비교 조건으로 변경가능하며, 위상차이는 최소값 기준으로 이동시켜 각 값의 Gap을 비교하여 같은 조건의 값인지를 판단 가능함.

참고