제일 작은 수 제거하기

문제정의

---

배열에서 제일 작은 수를 제거하여 출력한다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class RemoveMin {
    
    //프로그래머스 문제풀이 level1 제일 작은 수 제거하기
    public static void main(String[] args)
    {
        int[] arr = {4,3,2,1};
        
        ArrayList<Integer> sorted_list = new ArrayList<Integer>();
        for(int n : arr)
            sorted_list.add(n);
        ArrayList<Integer> unsorted_list = new ArrayList<Integer>();
        unsorted_list = (ArrayList<Integer>)sorted_list.clone();
        Collections.sort(sorted_list);
        
        Integer min = sorted_list.get(0);
        unsorted_list.remove(min);
        
        int[] answer = new int[unsorted_list.size() == 0 ? 1 : unsorted_list.size()];
        if(answer.length == 1)
            answer[0] = -1;
        else
        {
            for(int i = 0; i < unsorted_list.size(); i++)
                answer[i] = Integer.parseInt(unsorted_list.get(i).toString());
        }
    }
}

부분부분 살펴보자

int[] arr = {4,3,2,1};
        
    ArrayList<Integer> sorted_list = new ArrayList<Integer>();
    for(int n : arr)
        sorted_list.add(n);
    ArrayList<Integer> unsorted_list = new ArrayList<Integer>();
    unsorted_list = (ArrayList<Integer>)sorted_list.clone();
    Collections.sort(sorted_list);

어레이리스트를 두개 선언하였다. 하나는 정렬을 하고 하나는 정렬하지 않은 것이다. 배열 내에서 제일 작은 수를 알기 위해 정렬을 하는 것인데, 결과 배열은 순서가 흐트러지면 안되므로 두개의 배열을 선언한것이다. 여기서의 시간복잡도는 \(O(nlogn)\)이다.

Integer min = sorted_list.get(0);
unsorted_list.remove(min);

정렬한 배열의 첫번째 값을 가져와서 정렬하지 않은 배열에서 그 값을 제거한다. 시간복잡도는 \(O(n)\)이다.

int[] answer = new int[unsorted_list.size() == 0 ? 1 : unsorted_list.size()];
if(answer.length == 1)
    answer[0] = -1;
else
{
    for(int i = 0; i < unsorted_list.size(); i++)
        answer[i] = Integer.parseInt(unsorted_list.get(i).toString());
}

제거한 값을 배열로 만들기 위해 위 코드와 같이 처리한다. 값을 제거한 배열이 빈 배열일 경우 -1을 집어넣어야 하므로 사이즈를 1로 지정하고 그게 아니라면 결과 사이즈로 int배열을 선언한다. 정답 배열의 크기가 1일 경우 -1을 넣고 그게 아니라면 배열을 그대로 담는다. 시간복잡도는 \(O(n)\)이다. 따라서 전체 시간복잡도는 \(O(nlogn)\)이다.

테스트

테스트케이스는 전부 통과하였지만 만약 테스트케이스가 [1,1,3]인 경우 내 알고리즘은 틀리게 된다. 그래도 통과가 된걸보니 그러한 케이스는 없었던 것 같다.