[코딩테스트합격자되기-자바편] 문제01. 배열 정렬하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

내용

정수 배열을 정렬해서 반환하는 solution() 함수를 완성하세요.

 

제약 조건

• 정수 배열의 길이는 2 이상 10^5 이하입니다.
• 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.

 

입출력의 예

입력	출력
[1, -5, 2, 4, 3]	[-5, 1, 2, 3, 4]
[2, 1, 1, 3, 2, 5, 4]	[1, 1, 2, 2, 3, 4, 5]
[6, 1, 7]	[1, 6, 7]

 

 

 

 

---

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
23:21	23:42	21분

 

문제 분석

제약 사항 파악 & 테스트 케이스 작성

• 입출력 모두 정수 배열
• 정수 배열의 길이는 2 이상 10^5 이하
• 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하

정수 배열의 길이가 최대 $10^5$

• 제한시간이 3초라면 O(N^2)은 사용할 수 없습니다.

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

입력	출력
[1, -5, 2, 4, 3]	[-5, 1, 2, 3, 4]
[2, 1, 1, 3, 2, 5, 4]	[1, 1, 2, 2, 3, 4, 5]
[6, 1, 7]	[1, 6, 7]

 

 

입력값은 1차원 배열이고 출력값은 오름차순의 1차원 배열로 반환된다.

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(정수형배열) {
    Arrays.sort(정수형배열)
    return 정수형배열
}

// 배열의 최대 길이가 10^5 이므로 제한 시간이 3초일 경우 시간복잡도가 O(N^2)인 아래 식 사용할 수 없음
solution(정수형배열) {
    // bubble sort 이용
    for (i;정수형배열길이;++) {
        for(j=i+1;정수형배열길이;++) {
            if (정수형배열[i] > 정수형배열[j]) {
                임시저장소 = 정수형배열[i]
                정수형배열[i] = 정수형배열[j]
                정수형배열[j] = 임시저장소
            }
        }
    }
    return 정수형배열
}

 

 

구현

public static int[] solution(int[] arr) {  
    Arrays.sort(arr);  
    return arr;  
}

// 배열의 최대 길이가 10^5 이므로 제한 시간이 3초일 경우 시간복잡도가 O(N^2)인 아래 식 사용할 수 없음
public static int[] solution(int[] arr) {  
    // bubble sort 이용
    for (int i = 0; i < arr.length; i++) {  
        for (int j = i + 1; j < arr.length; j++) {  
            if (arr[i] > arr[j]) {  
                int temp = arr[i];  
                arr[i] = arr[j];  
                arr[j] = temp;  
            }  
        }  
    }  
    return arr;  
}

 

 

---

 

 

복기하기

답안과 나의 풀이를 비교해보세요

답안

 

원본 배열에서 바로 정렬

public static int[] solution(int[] arr) {
    Arrays.sort(arr); // 참고로 sort() API는 O(NlogN)의 시간복잡도를 가진다.
    return arr;  
}

 

원본 배열 두고 정렬

public static int[] solution(int[] arr) {
    int[] cloned = arr.clone();
    Arrays.sort(cloned);  
    return cloned;  
}

 

 

O(N^2)알고리즘 사용하여 정렬

public static int[] bubbleSort(int[] org) {  
    int[] arr = org.clone();
    int n = arr.length;
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n - i - 1; j++) {  
            if (arr[j] > arr[j + 1]) {  
                int temp = arr[i];  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
            }  
        }  
    }  
    return arr;  
}

 

 

---

 

요약하기

• sort() API는 O(NlogN)의 시간복잡도를 가진다.
• 원본 배열을 두고 복제 배열 생성을 원할 시 clone() API를 사용하자.