프로그래머스 - 제일 작은 수 제거하기[java]

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12935

문제 설명

파라미터로 받은 arr에서 제일 작은 수를 제거하고 나머지 값들을 리턴하고 값이 10 이며 -1을 리턴하면 되는 문제이다.

예시

입력 값: [4,3,2,1] ---> 리턴 값 [4,3,2]

문제 풀이

import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        if(arr.length == 1){
            arr[0] = -1;
            return arr;
        } else {
            int[] copy = Arrays.copyOf(arr, arr.length);
            Arrays.sort(copy);
            int min = copy[0];
            ArrayList<Integer> l = new ArrayList<Integer>();
            for(int i = 0; i < arr.length; i++) {
                if(arr[i] != min)
                    l.add(arr[i]);
            }
            int [] answer = new int[arr.length - 1];
            for(int j = 0; j < l.size(); j++) {
                answer[j] = l.get(j);
            }
            return answer;
        }
    }
}

sort를 써서 최소값을 쉽게 찾아내었고,
array를 copy하여 기존 파라미터에 저장된 원본 데이터를 보존 시켰다. 이후 arraylist를 활용해 리턴값의 형으로 변환 시켰다.

더 나은 풀이(코드 라인 수 최소화)

import java.util.Arrays;
import java.util.stream.Stream;
import java.util.List;
import java.util.ArrayList;

class Solution {
  public int[] solution(int[] arr) {
      if (arr.length <= 1) return new int[]{ -1 };
      int min = Arrays.stream(arr).min().getAsInt();
      return Arrays.stream(arr).filter(i -> i != min).toArray();
  }
}

stream과 filter를 이용해 3줄만에 끝내 버렸다....
속도는 상대적으로 좀 느리겠지만(참고 자료)
코딩테스트에서 유리할듯 싶다....

더 나은 풀이(시간 복잡도 효율화)

class Solution {
  public int[] solution(int[] arr) {
      if(arr.length == 1){
          int[] answer = {-1};
          return answer;
      }

      int[] answer = new int[arr.length-1];
      int minIndex=0;

      for(int i=0;i<arr.length;i++){
          if(arr[minIndex]>arr[i]){
              minIndex = i;
          }
      }
      for(int i=minIndex+1;i<arr.length;i++){
          arr[i-1] = arr[i];
      }
      for(int i=0;i<answer.length;i++){
          answer[i] = arr[i];
      }
      return answer;
  }
}

시간 복잡도 효율 측면에서 보았을때, 제일 나은거 같다.

총 3개의 for loop이라 O(n)으로 끝나므로 O(nlogn)의 sort()가 들어간 내가 짠 코드보단 일단 더 빠르다..