핵심 개념
배열의 특정 구간을 역순으로 만드는 알고리즘
static void reverse(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}동작 원리
양 끝에서 중앙으로
[1, 2, 3, 4, 5]
↕ ↕ (start=0, end=4)
↕ ↕ (start=1, end=3)
↕ (start=2, end=2) 종료핵심: 양 끝 요소를 교환하면서 포인터를 중앙으로 이동
코드 라인별 설명
1. while (start < end)
while (start < end) {조건의 의미:
start < end: 두 포인터가 만나지 않았을 때 계속 실행start == end: 같은 위치 도달 → 교환 불필요 → 종료start > end: 이미 교차 → 종료
왜 <=가 아니라 <일까?
start == end인 경우:
[1, 2, 3, 4, 5]
↕
start=end=2
자기 자신과 교환할 필요 없음!2. 교환 알고리즘 (swap)
int temp = arr[start]; // 1단계
arr[start] = arr[end]; // 2단계
arr[end] = temp; // 3단계단계별 실행:
초기: arr[start]=1, arr[end]=5
1단계: temp = arr[start] = 1
temp에 1 임시 저장
2단계: arr[start] = arr[end] = 5
왼쪽에 5 복사
배열: [5, 2, 3, 4, 5]
3단계: arr[end] = temp = 1
오른쪽에 1 복사
배열: [5, 2, 3, 4, 1]왜 temp 변수가 필요할까?
// temp 없이 하면?
arr[start] = arr[end]; // 1을 잃어버림!
arr[end] = arr[start]; // 둘 다 5가 됨 (실패)
// temp 사용
int temp = arr[start]; // 1을 보관
arr[start] = arr[end]; // 안전하게 5 복사
arr[end] = temp; // 보관한 1 복원 (성공)3. 포인터 이동
start++; // 왼쪽 포인터를 오른쪽으로
end--; // 오른쪽 포인터를 왼쪽으로이동 과정:
1회전: start=0, end=4 → 교환 → start=1, end=3
2회전: start=1, end=3 → 교환 → start=2, end=2
3회전: start=2, end=2 → 2 < 2는 거짓 → 종료실행 예제
예제 1: 홀수 개 배열
배열: [1, 2, 3, 4, 5]
목표: 전체 역순
초기 상태:
[1, 2, 3, 4, 5]
↑ ↑
start=0 end=4
1회전:
교환 전: [1, 2, 3, 4, 5]
교환 후: [5, 2, 3, 4, 1]
이동: start=1, end=3
2회전:
교환 전: [5, 2, 3, 4, 1]
교환 후: [5, 4, 3, 2, 1]
이동: start=2, end=2
3회전:
start=2, end=2
조건: 2 < 2 → 거짓 → 종료
최종: [5, 4, 3, 2, 1]중앙 요소(3)는 교환 안 함!
예제 2: 짝수 개 배열
배열: [1, 2, 3, 4, 5, 6]
1회전: [6, 2, 3, 4, 5, 1] (start=1, end=4)
2회전: [6, 5, 3, 4, 2, 1] (start=2, end=3)
3회전: [6, 5, 4, 3, 2, 1] (start=3, end=2)
start > end → 종료
최종: [6, 5, 4, 3, 2, 1]예제 3: 구간 역순
배열: [10, 20, 30, 40, 50]
인덱스: 0 1 2 3 4
reverse(arr, 1, 3) 실행
초기: start=1, end=3
[10, 20, 30, 40, 50]
↑ ↑
1회전: 20 ↔ 40
[10, 40, 30, 20, 50]
↑
start=2, end=2
start >= end → 종료
최종: [10, 40, 30, 20, 50]특수 케이스
케이스 1: 요소 1개
reverse(arr, 2, 2)
while (2 < 2) // 거짓
// 실행 안 됨
// 변화 없음케이스 2: 요소 2개
reverse(arr, 1, 2)
1회전만 실행:
arr[1] ↔ arr[2]
종료케이스 3: 빈 구간
reverse(arr, 3, 2) // start > end
while (3 < 2) // 거짓
// 실행 안 됨시간 복잡도
반복 횟수 = (end - start + 1) / 2
시간 복잡도 = O(n) // n = 구간 길이
공간 복잡도 = O(1) // temp 변수 하나만 사용왜 절반만 순회할까?
- 양 끝에서 동시에 접근
- 중앙에서 만나면 종료
- 효율적!
실전 문제 적용
백준 10813번: 바구니 뒤집기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] basket = new int[N + 1];
for (int i = 1; i <= N; i++) {
basket[i] = i;
}
for (int a = 0; a < M; a++) {
int i = sc.nextInt();
int j = sc.nextInt();
reverse(basket, i, j);
}
for (int i = 1; i <= N; i++) {
System.out.print(basket[i] + " ");
}
}
static void reverse(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}다른 구현 방법
방법 1: for문 사용
static void reverse(int[] arr, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}방법 2: 재귀
static void reverse(int[] arr, int start, int end) {
if (start >= end) return;
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
reverse(arr, start + 1, end - 1);
}방법 3: Collections.reverse() (리스트용)
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
Collections.reverse(list);주의사항
1. 인덱스 범위 확인
// 잘못된 호출
reverse(arr, -1, 10); // ArrayIndexOutOfBoundsException 가능
// 안전한 호출
if (start >= 0 && end < arr.length && start <= end) {
reverse(arr, start, end);
}2. 원본 배열 변경됨
int[] arr = {1, 2, 3, 4, 5};
reverse(arr, 0, 4);
// arr이 직접 변경됨!
// 복사본이 아님
System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]3. start > end인 경우
reverse(arr, 5, 2);
while (5 < 2) // 거짓
// 실행 안 됨 (에러는 아님)활용 예시
1. 문자열 뒤집기
String str = "hello";
char[] chars = str.toCharArray();
reverse(chars, 0, chars.length - 1);
String reversed = new String(chars); // "olleh"2. 배열 회전
// 배열을 k칸 왼쪽으로 회전
static void rotateLeft(int[] arr, int k) {
int n = arr.length;
k = k % n;
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
reverse(arr, 0, n - 1);
}3. 팰린드롬 검사
static boolean isPalindrome(String str) {
char[] chars = str.toCharArray();
int left = 0, right = chars.length - 1;
while (left < right) {
if (chars[left] != chars[right]) {
return false;
}
left++;
right--;
}
return true;
}정리
핵심 포인트
- 양 끝 교환 → 중앙으로 이동
- temp 변수로 안전하게 값 교환
- start < end 조건으로 중앙에서 종료
- 시간 복잡도 O(n), 공간 복잡도 O(1)
- 원본 배열을 직접 수정
반드시 기억할 것
while (start < end)- 등호 없음!- temp 변수 사용 필수
- 양쪽 포인터 모두 이동
- 구간 역순에도 동일하게 적용
자주 사용되는 곳
- 배열 뒤집기
- 문자열 뒤집기
- 배열 회전
- 팰린드롬 검사
- 백준 문제: 10813, 25305 등
reverse 함수는 투 포인터 알고리즘의 가장 기본이 되는 패턴!
뇽