[알고리즘/문제풀이] CodingBat Array-3 maxSpan

문제는 이곳에서 확인이 가능합니다.

간단히 말하면 int[]를 인자로 받아서 span의 최대값을 구하는 것입니다.

우선 span이라는 개념에 대해서 알아야 하는데요.

문제에서는 span이라는 것을 "가장 왼쪽에 있는 특정 값 a와 가장 오른쪽에 있는 동일한 값 a 사이의 길이" 라고 설명하고 있습니다. 이때 이 길이에는 가장 왼쪽값과 가장 오른쪽 값의 위치를 포함한 길이입니다.

즉, int[ 1, 2, 1 ] 을 인자로 받았을 경우 1에 대한 span은 3이 됩니다.

가장 왼쪽의 1과 가장 오른쪽의 1을 포함한 길이가 되는 것이죠.

만약 int[ 1, 2, 1, 3, 4, 2 ]를 인자로 받았다면,

1에 대한 span = 3

2에 대한 span = 5

3에 대한 span = 1

4에 대한 span = 1

이 됩니다.

이렇게 계산했을 때 maxSpan은 2에 대한 span값인 5가 됩니다.

제가 풀어본 해답은 아래와 같습니다.

뭐 그냥 루프를 중복으로 돌려서 해결했는데 이건 정말 최악의 해답이 되겠죠.

왠만하면 중복 루프를 사용하면 안됩니다. 속도저하가 상당하니까요.

문제에서 말하길 속도는 신경쓰지 않아도 된다고 해서 그냥 바로 생각나는 대로 문제를 풀어보았습니다.

 O(n제곱)이 되지 않도록 하기 위해서 이미 체크했던 숫자인지에 대한 정보를 가지고 있도록 했습니다.

위에서 든 예제를 인용해서 설명드리자면,

int [ 1, 2, 1, 3, 4, 2 ]를 인자로 받았을 경우에 1과 2는 각각 두번씩 들어가있는데요

이때 두번째로 나오는 숫자들에 대해서는 사실 계산할 필요가 없죠. 이미 첫번째로 나온 1과 2를 만났을 때 span값을 계산하기 때문이죠. 동일한 숫자들이 두개 이상 나오게된다면 이미 검사했던 숫자들에 대한 span을 구하기 위해서 불필요한 계산을 하게 됩니다. 이런 계산을 없애기 위해서 한번 체크했던 숫자와 동일한 숫자를 outer most for loop에서 만나게되면 체크했던 숫자인지를 검사하는 first inner loop를 돌고 체크했던 숫자가 아닌 경우에만 second inner loop에서 처리하게 됩니다.

또한, second inner루프에서 처리를 할 때에도 int[]의 현재 숫자의 위치에서 오른쪽에 있는 숫자들을 가지고 비교를 합니다. 좌측에 있는 숫자들 중에는 이 숫자와 동일한 숫자가 없다는 전제가 필요한데 이 전제를 바로 위에 설명드린 first inner loop에서 처리를 해주고 있기 때문이죠.

이런식으로 하게될 경우 최악의 경우( int[]에 들어있는 숫자가 모두 다를 경우 )에도 O(n제곱) 까지는 안가게 됩니다.

중복 for loop를 사용하기는 했지만 나름 속도도 신경을 쓴 로직이라고 말할 수 있죠.

public int maxSpan(int[] nums) {
  if ( nums.length == 0 ) return 0;
  int maxSpan = 1;
  int[] checkedNumbers = new int[nums.length];
  int checkedNumbersPos = 0;

 

  // Outer Most For Loop

  for ( int i = 0; i < nums.length ; i++ ){
     boolean checked = false;

     // First Inner Loop
     for( int checkedItem : checkedNumbers ){
        if ( checkedItem == nums[i] ){
           checked = true;
        }
     }
     if ( !checked ){
         checkedNumbers[checkedNumbersPos] = nums[i];

         // Second Inner Loop
         for ( int j = i + 1; j < nums.length ; j++ ){
            if ( nums[j] == nums[i] ){
               int tempSpan = j - i + 1;
               if ( tempSpan > maxSpan ){ maxSpan = tempSpan;}
            }
         }
     }
  }
  return maxSpan;
}