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

간략하게 한글로 문제를 번역하면 아래와 같습니다.

int[]를 인자로 받아서 3 바로 뒤에 4를 위치하도록 정렬한 뒤 결과를 리턴합니다.

인자로 들어온 int[]에서 숫자 3과 숫자4의 개수는 항상 동일하며, 숫자 3 뒤에는 항상 3과 4가 아닌 다른 수가 들어옵니다. 숫자3은 정렬할 수 없으며 다른 모든 수 들은 위치변경이 가능합니다. 또한, 첫 숫자 3은 항상 숫자 4보다 먼저 출현합니다.

보통 int[]보다는 List형태의 데이터를 다루기가 쉽습니다. 기본적으로 제공해주는 api가 사용하기 쉽기 때문이죠.

그래서 List를 사용했습니다.

우선 int[] 를 루프를 돌려서 (3 이 출현하는 위치 + 1)과 (4의 위치)가 어디인지를 두개의 ArrayList에 나눠서 넣었습니다.

어차피 3과 4의 출현 빈도가 동일하기 때문에 두개 리스트의 길이는 항상 동일하겠죠.

그렇게 루프를 한번 돌면서 위치정보를 갖고있다가, 위치정보 리스트를 루프돌면서 해당 위치의 숫자들의 위치를 서로 바꿔주면 되는 것이죠. ( 3의 위치 +1 )을 저장하는 이유는 3 바로 다음의 숫자와 4의 위치를 서로 바꿔줘야 하기 때문입니다.

저는 여기서 리스트를 두개를 사용했는데, 리스트하나에 맵객체를 넣어서 구현할 수도 있겠습니다. 맵에는 ( 3의 위치+1)과 4의 위치가 들어가겠죠.

public int[] fix34(int[] nums) {
  List<Integer> posOfFour = new ArrayList<Integer>();
  List<Integer> posOfThree = new ArrayList<Integer>();
  for ( int i = 0; i < nums.length; i++ ){
      if ( nums[i] == 4 ){
        posOfFour.add(i);
      }
      if ( nums[i] == 3 ){
         posOfThree.add(i+1);
      }
  }
  for ( int j = 0; j < posOfThree.size(); j++ ){
     int temp = nums[(int)posOfThree.get(j)];
     nums[(int)posOfThree.get(j)] = nums[(int)posOfFour.get(j)];
     nums[(int)posOfFour.get(j)] = temp;
  }
  return nums;
}

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

간단히 말하면 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;
}

문제는 이곳에 있습니다.

public int noTeenSum(int a, int b, int c) {
  int sum = 0;
  sum += fixTeen(a);
  sum += fixTeen(b);
  sum += fixTeen(c);
  return sum;
}
public int fixTeen(int n){
    if ( n > 12 && n < 20 ){
         if ( n != 15 && n != 16 ){
              return 0;
         }
    }
    return n;
}

코딩박쥐 닷컴의 문제풀이입니다. 물론 제가 직접 코딩한 것입니다.

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

public int luckySum(int a, int b, int c) {

  if ( a == 13 ){ return 0;}
  if ( b == 13 ){ return a;}
  if ( c == 13 ){ return a+b;}
  return a + b + c;
}

이번에는 코딩박쥐 닷컴의 loneSum 메소드를 구현해 보았습니다.

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

public int loneSum(int a, int b, int c) {
   int sum = 0;
   sum += a;
   if ( a == b ){
       sum -= b;
   }else{
       sum += b;
   }
   if ( a== c || b == c ){
       sum -= c;
   }else{

       sum+= c;

   }
   return ( sum < 0 ? 0 : sum );

}

[자바 알고리즘 문제]

이 문제는 일종의 online judge 사이트인 코딩뱃(코딩박쥐) 닷컴에 나와있는 문제입니다.

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

아래 해답은 제가 직접 코딩한 내용입니다.

public boolean makeBricks(int small, int big, int goal) {
  if ( (goal - small <= big*5) && ( goal%5 <= small ) ){
      return true;
  }
  return false;
}