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

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

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

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;
}