4주차
정렬은 데이터를 일정한 기준에 따라 순서대로 재배치하는 것으로 생각하면 됩니다. 대표적으로 오름차순, 내림차순 정렬이 있고, 코딩 테스트에서는 숫자뿐 아니라 문자열, 객체, 2차원 배열도 정렬합니다.
정렬을 하는 이유는 단순히 보기 좋게 만들기 위해서가 아니라, 실전에서는 보통 다음 목적 때문에 정렬합니다.
- 가장 작은 값, 가장 큰 값, k번째 값을 빠르게 파악하기 위해
- 중복 여부를 쉽게 확인하기 위해
- 가까운 값끼리 비교하기 위해
- 이후에 투 포인터, 그리디, 이진 탐색 같은 기법을 적용하기 위해
즉, 정렬은 그 자체가 목적일 때도 있지만, 대부분은 문제를 풀기 위한 전처리 도구로 사용됩니다.
- 단순 정렬(버블, 선택, 삽입): 보통
O(N^2) - 실전 내장 정렬: 대체로
O(N log N)
코딩 테스트에서는 직접 버블 정렬, 선택 정렬을 구현하는 경우보다 언어 내장 정렬을 올바르게 사용하는 능력이 훨씬 중요합니다.
대부분의 코딩 테스트에서는 정렬을 실제로 구현하는 경우는 드물기 때문입니다.
Java를 기준으로 설명한다면, 기본적으로 제공되는 정렬 API는 3가지 입니다.
| 구분 | 기본형 배열 정렬 | 객체 배열 / 리스트 정렬 |
|---|---|---|
| 대표 API |
Arrays.sort(int[]), Arrays.sort(long[]) 등 |
Arrays.sort(Object[]), Collections.sort(List), List.sort()
|
| 실제 구현 계열 | Dual-Pivot Quicksort |
TimSort 계열 merge sort
|
| 주요 특징 | 빠름 | 안정 정렬(stable) |
| stable 여부 | 아님 | 맞음 |
| 같은 값의 기존 순서 유지 | 보장하지 않음 | 보장함 |
| 유리한 상황 | 단순 숫자/기본형 데이터 정렬 | 객체 정렬, 다중 조건 정렬, 일부 정렬된 데이터 |
| 복잡한 비교 기준 적용 | 불가능 또는 제한적 |
Comparator로 유연하게 가능 |
| 코딩 테스트 관점 | 숫자 배열 정렬에 자주 사용 | 문자열, 객체, 사용자 정의 기준 정렬에 자주 사용 |
해당 표를 참고하여, 차이점을 파악해 실제 코드 작성 시 필요한 메서드만 이용해 빠르게 구현이 가능합니다.
탐색은 원하는 값이나 조건에 맞는 데이터를 찾는 것입니다.
예를 들면 다음과 같은데,
- 특정 값이 배열에 존재하는가
- 특정 값의 위치는 어디인가
- 조건을 만족하는 첫 번째 원소는 무엇인가
- 가장 큰 값, 가장 작은 값은 무엇인가
입니다.
탐색은 단순히 “찾는다”로 끝나지 않고, 코딩 테스트에서는 어떤 방식으로 찾을지 선택하는 것이 핵심이 됩니다.
- 선형 탐색: 앞에서부터 순차적으로 하나씩 확인
- 해시 기반 탐색: Set, Map으로 빠르게 존재 여부 확인
- 정렬 후 탐색: 정렬된 상태를 활용해 더 빠르게 찾기
-
이진 탐색: 정렬된 데이터에서 반씩 줄여가며 탐색
→ 10주차 Binary Search에서 자세히 다룰 예정
Sorting / Searching은 서로 많은 연관을 가지는 관계입니다.
예를 들어,
- 정렬 후 인접 원소끼리 비교 → 최소 차이, 중복 확인
- 정렬 후 범위 확인 → 투 포인터 적용 가능
- 정렬 후 특정 값 찾기 → 이진 탐색 가능
그래서 코딩 테스트에서는 종종 이런 흐름이 주로 나옵니다.
정렬 → 구조가 단순해짐 → 탐색/비교/조건처리가 쉬워짐
가장 기본적인 형태입니다.
문제 예시 형태
- 숫자를 오름차순으로 정렬하라
- 문자열을 사전순으로 정렬하라
- 내림차순으로 정렬하라
핵심 포인트
- 내장 정렬 함수 사용
- 숫자 정렬과 문자열 정렬의 차이 구분
- 오름차순 / 내림차순 처리법 숙지
실전에서 매우 자주 나오는 패턴 중 하나입니다.
문제 예시 형태
- 점수를 기준으로 내림차순 정렬
- 길이가 짧은 문자열부터 정렬
- x좌표 오름차순, 같으면 y좌표 오름차순
- 나이 오름차순, 같으면 가입 순서 유지
핵심 포인트
- 정렬 기준이 하나인지 여러 개인지 확인
- 같을 때의 처리(2차 기준)까지 꼭 작성
- 비교 함수(comparator) / key 함수나 람다 함수에 익숙해져야 함
가장 기본적인 탐색입니다.
문제 예시 형태
- 특정 값이 있는가
- 특정 값의 위치는 어디인가
- 처음 등장하는 위치는 어디인가
핵심 포인트
- 배열을 앞에서부터 순회
- 데이터 크기가 작거나 1회성 탐색일 때 적절
- 시간복잡도는
O(N)
조건 기반 탐색 문제입니다.
문제 예시 형태
- 가장 큰 값 찾기
- 가장 작은 값 찾기
- 처음으로 100 이상이 되는 값 찾기
핵심 포인트
- 순회하면서 조건 검사
- 갱신 조건을 정확히 작성
- 초기값 설정 실수 주의
이 경우 선형 탐색만 하면 비효율적일 수 있습니다.
문제 예시 형태
- 특정 수가 배열에 있는지 여러 번 물어봄
- 중복 체크를 반복해야 함
핵심 포인트
- 한 번 찾는 문제면 선형 탐색도 가능
- 여러 번 찾는 문제면 Set / Map이 훨씬 유리
- 탐색은 “찾는 행위”보다 “찾는 전략 선택”이 중요함
https://school.programmers.co.kr/learn/courses/30/lessons/42748
이 문제는 핵심 조건을 만족하도록 자료를 한 번씩 확인하며 처리하는 방식입니다.
- 입력 데이터를 문제 조건에 맞게 순회한다.
- 필요한 값은 별도의 변수(또는 자료구조)에 저장하면서 갱신한다.
- 조건을 만족하는 경우 정답을 증가시키거나 결과를 업데이트한다.
- 모든 탐색이 끝나면 최종 결과를 반환한다.
import java.util.Arrays;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for (int idx = 0; idx < commands.length; idx++) {
int i = commands[idx][0];
int j = commands[idx][1];
int k = commands[idx][2];
int[] temp = Arrays.copyOfRange(array, i - 1, j);
Arrays.sort(temp);
answer[idx] = temp[k - 1];
}
return answer;
}
}def solution(array, commands):
answer = []
for i, j, k in commands:
temp = sorted(array[i - 1:j])
answer.append(temp[k - 1])
return answerfunction solution(array, commands) {
const answer = [];
for (const [i, j, k] of commands) {
const temp = array.slice(i - 1, j).sort((a, b) => a - b);
answer.push(temp[k - 1]);
}
return answer;
}- 정렬 기준을 문제 조건대로 정확히 반영하지 않고, 오름차순/내림차순이나
2차 기준을 빠뜨리는 경우를 조심해야 합니다. - 정렬 후에는 원래 인덱스나 입력 순서 정보가 바뀔 수 있으므로, 필요한 경우 값과 인덱스를 함께 저장해야 합니다.
- 숫자 정렬과 문자열 정렬을 혼동하면 의도와 다른 결과가 나올 수 있으니 차이점을 제대로 알고 있어야 합니다.
- 탐색 범위나 시작/끝 인덱스를 잘못 설정하면 오류가 자주 발생합니다.
- 정렬이 꼭 필요한 문제인지 확인하지 않고 무조건 정렬부터 하면 불필요한 시간 복잡도가 추가될 수 있습니다.