[코딩테스트/알고리즘 맛집] 자바 정렬(Sort) 코딩테스트에서 자주 나오는 문제 유형과 풀이 팁

정렬(Sort)

개요

데이터를 오름차순 또는 내림차순으로 배열하거나 리스트의 요소를 정렬하는 과정이다. 

 

정렬을 활용한 코딩테스트 문제는 매우 다양하다. 정렬 문제는 문제를 풀 때는 정렬 기준을 정확히 파악하고, 그에 맞는 알고리즘을 선택하는 것이 중요하다. 정렬 알고리즘, 이진 탐색, 투 포인터, 빈도수 계산 등 다양한 기술을 조합해 해결해야 하는 문제들이 많다. 

 

주어진 조건을 Arrays.sort() 를 이용해서 정렬해야 하는 문제도 있고, 정렬 기준을 사용자 정의 객체에 맞게 지정해야 하는 경우, Comparator 인터페이스를 구현한 객체를 Collections.sort() 또는 Arrays.sort()에 전달하여 정렬하면 되고, 이 때 Java 8 이상에서는 Comparator를 람다 표현식으로 쉽게 작성할 수 있다.

[Java] 배열 사용자정의 정렬하는 법(내림차순, 람다식)

 

✅ 정렬 기준

• 정렬 기준을 잘 파악하고, 자주 나오는 조건을 이해해야 한다.
• 예를 들어, "숫자가 작은 순으로 정렬" 또는 "문자열 길이가 짧은 순으로 정렬"과 같은 조건을 정확히 읽고 구현하는 것이 중요하다.

✅ 시간복잡도

• 시간 복잡도를 고려하여 정렬을 수행한다.
• 최악의 경우에도 O(n log n)의 성능을 내는 정렬을 선택하는 것이 유리하다. 

✅ 코딩테스트 문제 유형

• 기본 정렬: 배열을 오름차순 또는 내림차순으로 정렬하는 문제.
• 이진 탐색: 정렬된 배열에서 특정 값을 찾는 문제
• 두 수의 합: 두 수의 합이 특정 값이 되는 두 인덱스를 찾는 문제 (투 포인터 기법 활용)
• 배열에서 중복된 요소를 제거하고 정렬하는 문제
• 다양한 정렬 기준 (Comparator 사용): 객체의 여러 속성으로 정렬하는 문제
• K번째 큰/작은 수 찾기: 배열에서 K번째로 큰 또는 작은 값을 찾는 문제
• 두 개의 정렬된 배열을 합쳐 정렬된 배열을 만드는 문제
• 배열의 숫자 빈도를 계산하고 빈도수대로 정렬하는 문제
• 시간/날짜 정렬

예제 1 - K번째수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요

 

제한 조건

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

 

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

 

요점

• 주어진 범위(i, j)로 배열을 자르고, 그 부분의 배열을 정렬한 뒤, k번째 숫자를 구하는 작업을 리스트 슬라이싱과 정렬을 이용하여 처리한다.

 

소스코드

package Algorithm_02_Sort;

import java.util.Arrays;

public class Q02_1_KthNumber {

	public static void main(String[] args) {
		// 테스트 데이터
		int[] array = { 1, 5, 2, 6, 3, 7, 4 };
		int[][] commands = { { 2, 5, 3 }, // array[1:5] → {5,2,6,3} → 정렬 후 {2,3,5,6} → 3번째 숫자는 5
				{ 4, 4, 1 }, // array[3:4] → {6} → 정렬 후 {6} → 1번째 숫자는 6
				{ 1, 7, 3 } // array[0:7] → {1,5,2,6,3,7,4} → 정렬 후 {1,2,3,4,5,6,7} → 3번째 숫자는 3
		};

		// solution 메서드 실행
		Q02_1_KthNumber solution = new Q02_1_KthNumber();
		int[] result = solution.solution(array, commands);

		// 결과 출력
		System.out.println(Arrays.toString(result)); // [5, 6, 3]
	}

	public int[] solution(int[] array, int[][] commands) {
		// 프로그래머스 K번째 수
		// 1. 결과값 담아줄 정수형 배열 result 선언
		int[] result = new int[commands.length];
		for (int i = 0; i < commands.length; i++) {
			// 2. array 배열 돌면서 각 commands 요소의
			// i번째숫자, j번째숫자를 인자로 슬라이싱
			// 슬라이싱한 배열을 slicedArray에 담아줌
			int[] slicedArray = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);

			// 3. 자른 배열 오름차순 정렬
			Arrays.sort(slicedArray);
			// 4. result에 slicedArray의 k번째 숫자 집어 넣기
			result[i] = slicedArray[commands[i][2] - 1];
		}
		return result;
	}
}

 

예제 2 - 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

요점

• 주어진 숫자들을 문자열로 바꾸고, 두 숫자의 조합이 더 큰 값을 만들도록 정렬 기준을 사용자 정의하여 가장 큰 수를 만든다. 숫자들끼리 결합했을 때 더 큰 값을 만드는 순서대로 정렬하고, 그 결과를 이어붙이면 된다. 

소스 코드

package Algorithm_02_Sort;

import java.util.Arrays;

public class Q02_2_maximumNumber {

	public static void main(String[] args) {
		// 테스트 데이터
		String[] arr1 = { "3", "30", "34", "5", "9" };
		String[] arr2 = { "10", "2" };
		String[] arr3 = { "0", "0", "0" }; // 예외 케이스: "000" → "0"으로 처리 필요
		String[] arr4 = { "1", "20", "23", "4", "8" };

		// 테스트 실행
		System.out.println(getLargestNumber(arr1)); // 9534330
		System.out.println(getLargestNumber(arr2)); // 210
		System.out.println(getLargestNumber(arr3)); // 0
		System.out.println(getLargestNumber(arr4)); // 8423201
	}

	public static String getLargestNumber(String[] arr) {
		// 프로그래머스 가장 큰 수
		// 문자열 정렬 (내림차순, o2+o1과 o1+o2를 비교)
		Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

		// 예외 처리: 배열이 "0"으로만 구성된 경우 → "0" 반환
		if (arr[0].equals("0"))
			return "0";

		// 정렬된 결과를 하나의 문자열로 결합
		StringBuilder result = new StringBuilder();
		for (String str : arr) {
			result.append(str);
		}

		return result.toString();
	}

}

 

예제 3 - H-Index

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

 

입출력 예

citations	return
[3, 0, 6, 1, 5]	3

 

요점

• 논문들의 인용 횟수를 내림차순으로 정렬한 뒤, 각 논문에 대해 인용 횟수가 그 위치보다 크거나 같은지를 체크하여 최대 h값을 찾아내는 방식으로 H-Index를 구한다. 

 

소스 코드

package Algorithm_02_Sort;

import java.util.Arrays;

public class Q02_3_HIndex {
    public static void main(String[] args) {
        // 테스트 데이터
        int[] citations1 = {3, 0, 6, 1, 5};  // 예상 결과: 3
        int[] citations2 = {10, 8, 5, 4, 3}; // 예상 결과: 4
        int[] citations3 = {25, 8, 5, 3, 3}; // 예상 결과: 3
        int[] citations4 = {0, 0, 0, 0, 0};  // 예상 결과: 0
        int[] citations5 = {6, 6, 6, 6, 6};  // 예상 결과: 5

        // solution 메서드 실행
        Q02_3_HIndex solution = new Q02_3_HIndex();

        System.out.println(solution.solution(citations1)); // 3
        System.out.println(solution.solution(citations2)); // 4
        System.out.println(solution.solution(citations3)); // 3
        System.out.println(solution.solution(citations4)); // 0
        System.out.println(solution.solution(citations5)); // 5
    }

    public int solution(int[] citations) {
    	// 프로그래머스 H-INDEX
        // 결과값 담을 정수형 변수 초기화
        int answer = 0;

        // 배열 오름차순 정렬
        Arrays.sort(citations);

        // 배열 순회하여 H-Index 찾기
        for (int i = 0; i < citations.length; i++) {
            // 남은 논문의 수
            int h = citations.length - i;

            // 현재 인용된 논문 수가 h 이상이면 H-Index 갱신
            if (citations[i] >= h) {
                answer = h;
                break;
            }
        }
        return answer;
    }
}

 

예제 4 - 두 수의 합이 특정 값이 되는 경우 (투 포인터 기법)

주어진 배열에서 두 수의 합이 특정 값이 되는 인덱스를 찾으라.

소스 코드 

Arrays.sort(arr);  // 먼저 배열을 정렬
int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        System.out.println(left + ", " + right);
        break;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

 

예제 5 -  배열에서 중복을 제거한 후 정렬

배열에서 중복된 요소를 제거하고, 오름차순으로 정렬하라.

소스 코드 

int[] arr = {5, 2, 9, 1, 5, 6};
Set<Integer> uniqueElements = new HashSet<>();
for (int num : arr) {
    uniqueElements.add(num);
}
int[] result = uniqueElements.stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(result);

 

예제 6 - 정렬 기준이 여러 개인 경우 (Comparator 사용)

학생 객체들을 점수 순으로 정렬하되, 점수가 같으면 이름을 알파벳 순으로 정렬하라.

소스 코드 

import java.util.*;

class Student {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
            new Student("Alice", 90),
            new Student("Bob", 80),
            new Student("Charlie", 90)
        );

        students.sort(Comparator.comparingInt((Student s) -> s.score)
            .thenComparing(s -> s.name));

        for (Student student : students) {
            System.out.println(student.name + ": " + student.score);
        }
    }
}

 

예제 7 - 두 배열 합치기

두 개의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만들라.

소스 코드

int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};
int[] result = new int[arr1.length + arr2.length];
int i = 0, j = 0, k = 0;
while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
        result[k++] = arr1[i++];
    } else {
        result[k++] = arr2[j++];
    }
}
while (i < arr1.length) {
    result[k++] = arr1[i++];
}
while (j < arr2.length) {
    result[k++] = arr2[j++];
}

 

예제 8 - 자주 등장하는 숫자 찾기 (빈도수 정렬)

배열에서 자주 등장하는 숫자 순으로 정렬하라.

* 배열에서 각 숫자가 몇 번 등장하는지 구하고, 그 빈도수를 기준으로 정렬하는 문제이다. 이 문제는 Map을 활용하여 각 숫자의 빈도를 구하고, 빈도수대로 정렬한다.

 소스 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 3, 1, 3, 2, 1};

        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(freqMap.entrySet());
        list.sort((entry1, entry2) -> entry2.getValue() - entry1.getValue());

        for (Map.Entry<Integer, Integer> entry : list) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

 

예제 9 - 시간이나 날짜 기준으로 정렬하기 (시간/날짜 정렬)

주어진 날짜 배열을 오름차순으로 정렬하라.

*LocalDateTime 또는 SimpleDateFormat 클래스를 사용하여 날짜나 시간을 처리한다. 

소스 코드

import java.time.LocalDate;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        LocalDate[] dates = {
            LocalDate.of(2022, 3, 1),
            LocalDate.of(2021, 5, 12),
            LocalDate.of(2023, 1, 25)
        };

        Arrays.sort(dates);
        for (LocalDate date : dates) {
            System.out.println(date);
        }
    }
}

 

정렬 예제를 풀어본 후

자바에서 정렬을 구현할 때, 대부분 객체 배열 형식으로 나오는데 이 때 사용자 정의 객체를 정렬하려면 Comparator를 잘 활용해야 한다. 

Arrays.sort(array, new Comparator<YourClass>() {
    @Override
    public int compare(YourClass o1, YourClass o2) {
        return Integer.compare(o1.getValue(), o2.getValue());
    }
});

자바 8부터 제공되는 Lambda 표현식을 사용하면 객체의 특정 필드를 기준으로 정렬할 때 Comparator를 간결하게 구현할 수 있다.

Arrays.sort(array, (o1, o2) -> Integer.compare(o1.getValue(), o2.getValue()));

정렬 기준을 확실히 하자. 문제에서 요구하는 정렬 기준이 무엇인지 정확하게 파악하고, Comparator나 Comparable을 적절히 사용하자. 이 때 자주 발생하는 실수는 오름차순인지 내림차순인지 헷갈리는 것이다. 프로그래밍에서 디폴트는 오름차순이기 때문에, 내림차순 정렬을 할 때는 Comparator.reverseOrder()나 Collections.reverseOrder()를 써서 정렬한다. 

그리고 배열이나 리스트를 정렬할 때, 중복된 값이 있을 수 있기 때문에 중복처리를 해야 하는 경우는, HashSet을 사용하는데 이 때 먼저 중복을 제거하거나, 정렬 후 중복을 처리하는 방법을 고려해야 한다.

 

그리고 공부하다 보니 Stream API로 정렬하는 법도 알게 되었다.

 

아래는 코테 문제 풀면서 다른 분들이 Stream 으로 정렬한 걸 보고, 스트림으로 정렬하는 법을 찾아서 정리한 내용이다. 정리를 다 하고 나서 자료 조사를 좀 더 해 보니,

 

⭐Stream API를 이용한 정렬은 속도가 너무 느리기 때문에 코딩테스트에서는 피하는 것이 좋다고 한다.⭐

 

Stream으로 정렬하는 법

Stream을 활용하면 정렬뿐만 아니라 필터링, 매핑 등 다양한 기능들을 체이닝하여 깔끔한 코드로 처리할 수 있다. 하지만 이 때 주의 할 점은 스트림에서 정렬을 하고 나서 필요에 따라 다시 형변환을 해야 한다는 것이다. 

 

오름차순

List<YourClass> list = Arrays.asList(new YourClass(3), new YourClass(1), new YourClass(2));
list = list.stream()
           .sorted(Comparator.comparing(YourClass::getValue))  // YourClass의 getValue() 기준으로 오름차순 정렬
           .collect(Collectors.toList());

내림차순

List<YourClass> list = Arrays.asList(new YourClass(3), new YourClass(1), new YourClass(2));
list = list.stream()
           .sorted(Comparator.comparing(YourClass::getValue).reversed())  // 오름차순을 반전시켜 내림차순 정렬
           .collect(Collectors.toList());

Comparator.comparing 대신 람다 표현식으로 정렬하기

List<YourClass> list = Arrays.asList(new YourClass(3), new YourClass(1), new YourClass(2));
list = list.stream()
           .sorted((o1, o2) -> Integer.compare(o1.getValue(), o2.getValue()))  // 람다 표현식으로 오름차순 정렬
           .collect(Collectors.toList());

 

Stream을 정렬한 후 반환되는 결과는 Stream 타입이다. 즉, 정렬 작업을 스트림에서 수행한 후에는, 그 결과 역시 스트림 객체로 반환된다. 이걸 필요에 따라 컬렉션 타입(리스트, 배열 등)으로 변환하려면 collect()나 toArray() 같은 메서드를 사용해야 한다. 그리고 정렬 후 중복을 제거하려면 Set 타입으로 변환해야 하는데 중복을 제거하는 특성을 가진 HashSet을 사용한다. 

Stream → List로 변환하기: collect(Collectors.toList())

// 오름차순 정렬 후 리스트로 변환
List<YourClass> sortedList = list.stream()
     .sorted(Comparator.comparing(YourClass::getValue))
     .collect(Collectors.toList()); // 리스트로 변환

System.out.println("오름차순 정렬 후 리스트: " + sortedList);

Stream → 배열로 변환하기: toArray()

이 때, (YourClass[]::new와 같이 배열의 타입을 지정해야 한다)

// 오름차순 정렬 후 배열로 변환
YourClass[] sortedArray = list.stream()
    .sorted(Comparator.comparing(YourClass::getValue))
    .toArray(YourClass[]::new);  // 배열로 변환

System.out.println("오름차순 정렬 후 배열: " + Arrays.toString(sortedArray));

Stream → Set으로 변환하기: collect(Collectors.toSet()) 

// 오름차순 정렬 후 Set으로 변환 (중복 제거)
Set<YourClass> sortedSet = list.stream()
    .sorted(Comparator.comparing(YourClass::getValue))
    .collect(Collectors.toSet()); // Set으로 변환

System.out.println("오름차순 정렬 후 Set: " + sortedSet);

 

GitHub: https://github.com/awesomepossumgirl/coding-test/tree/main/coding-test/src/Algorithm_02_Sort

문제 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/parts/12244 

---

원래는 직접 정리하려고 했으나, 잘 정리된 글을 스크랩 해 왔습니다.

 

✔️삽입정렬

[알고리즘] 삽입정렬(insertion Sort) - JAVA(자바)

 

자바 [JAVA] - 삽입 정렬 (Insertion Sort)

 

✔️선택정렬

[알고리즘] 선택정렬(Selection Sort) - Java(자바)

 

✔️버블정렬

[알고리즘] 버블정렬(Bubble Sort) - JAVA(자바)

 

✔️병합 정렬

 

[알고리즘] 합병정렬(Merge Sort) - JAVA

 

✔️퀵정렬

[알고리즘] 퀵 정렬(Quick Sort) - JAVA(자바)

 

✔️힙정렬

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

 

✔️이진 탐색

[알고리즘] 이진 탐색(Binary Search) - JAVA(자바)

 

✔️투포인터

[알고리즘] 투 포인터(Two Pointer) - JAVA(자바)

 

✔️ Comparable와 Comparator 차이

Java 코딩 테스트 준비 - 정렬하는 방법, Comparable와 Comparator

 

✔️ 코딩테스트에서 Stream 쓰지 마세요

[Java] Stream은 왜 존재할까? (feat.코테에서 Stream 쓰지 마세요)