Practice1 0, 1, 2 로 이루어진 요소들로만 정렬하기
import java.util.Arrays;
public class Practice1 {
public static void solution(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int[] cntArr = new int[3];
for (int i = 0; i < arr.length; i++) {
cntArr[arr[i]]++;
}
int idx = 0;
for (int i = 0; i < cntArr.length; i++) {
while (cntArr[i] > 0) {
arr[idx++] = i;
cntArr[i] -= 1;
}
}
}
public static void main(String[] args) {
// Test code
int[] arr = {2, 0, 2, 1, 1, 0};
solution(arr);
System.out.println(Arrays.toString(arr));
System.out.println();
arr = new int[]{2, 0, 1};
solution(arr);
System.out.println(Arrays.toString(arr));
}
}-
입력 배열이 null 이거나 길이가 0 이면 바로 반환
-
cnrArr 배열을 만들어 0, 1, 2의 갯수를 세어줌
-
cntArr 를 이용해 원래 배열을 정렬된 형태로 재구성
Practice2 아나그램 (anagram) 찾기
import java.util.ArrayList;
import java.util.HashMap;
public class Practice2 {
public static ArrayList<ArrayList<String>> solution(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
HashMap<String, ArrayList<String>> map = new HashMap<>();
for (String s : strs) {
char[] cArr = s.toCharArray();
sort(cArr);
String key = String.valueOf(cArr);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}
public static void sort(char[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
char tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
}
}
public static void main(String[] args) {
// Test code
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
System.out.println(solution(strs));
strs = new String[]{"abc", "bac", "bca", "xyz", "zyx", "aaa"};
System.out.println(solution(strs));
}
}-
입력 검사
-입력 배열이 null 이거나 비어있는 경우, 빈 ArrayList를 반환 -
해시맵 생성
-문자열을 정렬하여 키로 사용하고, 같은 키를 가진 단어들을 ArrayList에 저장하는 HashMap을 생성 -
문자 정렬 및 맵에 저장
-각 문자열을 문자 배열로 변환하고, 이를 정렬하여 키를 생성
-정렬된 문자 배열을 문자열로 변환하여 해시맵의 키로 사용
-해시맵에 해당 키가 없으면 새로운 ArrayList를 생성하여 추가하고, 현재 단어를 ArrayList에 추가 -
해시맵의 값 변환
-해시맵의 값들을 ArrayList로 변환하여 반환 -
시간복잡도 : 각 단어의 길이를 m, 단어의 갯수를 n 이라고 할 때, O(n * m log m)이 됨. 각 단어를 정렬하는데 O(m log m) 시간이 걸리고, n개의 단어에 대해 반복되기 때문
Practice3 주어진 간격(intervals) 배열에서 간격을 병합하여 최종적으로 겹치지 않는 간격만 남기기
import java.util.ArrayList;
import java.util.Arrays;
public class Practice3 {
public static ArrayList<int[]> solution(int[][] intervals) {
if (intervals == null || intervals.length < 2) {
return new ArrayList<>();
}
sort(intervals);
ArrayList<int[]> result = new ArrayList<>();
int[] curInterval = intervals[0];
result.add(curInterval);
for (int i = 0; i < intervals.length; i++) {
if (curInterval[1] >= intervals[i][0]) {
curInterval[1] = intervals[i][1];
} else {
curInterval = intervals[i];
result.add(curInterval);
}
}
return result;
}
public static void sort(int[][] intervals) {
quickSort(intervals, 0, intervals.length - 1);
}
public static void quickSort(int[][] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(arr, left, right);
quickSort(arr,left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[][] arr, int left, int right) {
int pivot = arr[left][0];
int i = left;
int j = right;
while (i < j) {
while (arr[j][0] > pivot && i < j) {
j--;
}
while (arr[i][0] <= pivot && i < j) {
i++;
}
swap(arr, i, j);
}
swap(arr, left, i);
return i;
}
public static void swap(int[][] arr, int i, int j) {
int[] tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
// Test code
int[][] intervals = {{2, 6}, {1, 3}, {15, 18}, {8, 10}};
for (int[] item: solution(intervals)) {
System.out.print(Arrays.toString(item) + " ");
}
System.out.println();
}
}-
solution 메서드
-주어진 간격 배열(intervals) 이 null 이거나 길이가 2보다 작으면 빈 ArrayLIst를 반환
-간격을 정렬하기 위해 sort(intervals) 메서드 호출
-정렬된 간격을 저장할 result ArrayList 생성
-첫 번째 간격을 현재 간격(curIntervals) 으로 설정하고 result에 추가
-배열을 순회하면서 현재 간격과 겹치는 경우 간격을 병합하고, 그렇지 않은 경우 새로운 간격으로 간주하여 result 에 추가 -
sort 메서드
-간격을 시작점을 기준으로 퀵 정렬함. quickSort(intervals, 0, intervals.length - 1) 을 호출 -
quickSort 메서드
-배열을 분할하고 정복하는 전형적인 퀵 정렬 방식. 배열을 특정 pivot을 기준으로 분할하고 재귀적으로 정렬 -
partition 메서드
-주어진 배열을 pivot을 기준으로 분할하는 메서드. 이 코드에서는 간격의 시작점을 pivot으로 설정하여 분할 -
swap 메서드
-배열의 두 요소를 교환하는 유틸리티 메서드
Practice4 배열에서 부분적으로 정렬되지 않은 부분의 길이를 구하는 문제
public class Practice4 {
public static int solution(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int min = Integer.MAX_VALUE;
int firstIdx = 0;
for (int i = nums.length - 1; i >= 0; i--) {
min = Math.min(min, nums[i]);
if (nums[i] > min) {
firstIdx = i;
}
}
int max = Integer.MIN_VALUE;
int lastIdx = -1;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
if (nums[i] < max) {
lastIdx = i;
}
}
return lastIdx - firstIdx + 1;
}
public static void main(String[] args) {
// Test code
int[] nums = {2, 6, 4, 8, 5, 3, 9, 10};
System.out.println(solution(nums));
nums = new int[]{1, 3, 1};
System.out.println(solution(nums));
nums = new int[]{1, 9, 3, 4, 5};
System.out.println(solution(nums));
nums = new int[]{1, 2, 3, 4, 5};
System.out.println(solution(nums));
}
}-
solution 메서드
-배열이 null 이거나 길이가 2보다 작으면 0을 반환
-배열을 뒤에서부터 순회하면서 각 원소와 현재까지의 최소값을 비교하여 정렬되지 않은 구간의 시작 인덱스를 찾음
-배열을 앞에서부터 순회하면서 각 원소와 현재까지의 최대값을 비교하여 정렬되지 않은 구간의 끝 인덱스를 찾음
-구한 시작 인덱스와 끝 인덱스를 이용하여 부분적으로 정렬되지 않은 구간의 길이를 계산 -
변수 초기화
-min 을 Interger.MAX_VALUE 로 초기화 하고, 배열의 뒤에서부터 순회하면서 현재 원소와 min값을 비교하여 최소값을 갱신. min 값보다 큰 원소가 나오면 그 인덱스를 firstIdx로 설정.
-max 를 Integer.MIN_VALUE 로 초기화 하고, 배열의 앞에서부터 순회하면서 현재 원소와 max 값을 비교하여 최대값을 갱신. max 값보다 작은 원소가 나오면 그 인덱스를 lastIdx로 설정. -
부분적으로 정렬되지 않은 구간 길이 계산
-lasgIdx 에서 firstIdx를 빼고 1을 더하여 부분적으로 정렬되지 않은 구간의 길이를 반환
