인프런 알고리즘 강좌 5개 강좌 수강 및 문제 풀이 후 github에 push
1. 선택 정렬
package inflearn.sorting_searching;
import java.util.Arrays;
import java.util.Scanner;
public class P06_01 {
public static String solution(int n, int[] arr) {
/*
* [선택 정렬]
* 2중 for-loop을 사용해 0번 index부터 n-1 index까지 매 원소를 기준으로 잡고
* 기준 원소 우측에 남은 원소 중 가장 작은 원소를 해당 기준 원소와 swap 하며 정렬한다.
* 시간 복잡도 : O(n^2)
*/
int idx; // i 고정 상태에서, i보다 우측 원소 중 가장 작은 원소의 idx를 기록
for (int i = 0; i < n - 1; i++) {
idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[idx]) idx = j;
}
// swap
int tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
return Arrays.toString(arr).replaceAll("[^0-9 ]", "");
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); // buffer clear
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(solution(n, arr));
}
}
2. 버블 정렬
package inflearn.sorting_searching;
import java.util.Arrays;
import java.util.Scanner;
public class P06_02 {
public static String solution(int n, int[] arr) {
/*
* [버블 정렬]
* 선택 정렬과 반대로 우측 끝부터 고정시키는 방식으로 정렬
* i=0부터 계속 증가시키며 이웃한 원소와 자신을 비교하여 우측 원소가 자신보다 작으면 swap (오름차순 기준)
* 우측 끝이 한 원소 씩 고정되므로 반복 1회 수행 시 마다 끝을 1씩 줄여나가며 반복한다.
* 시간 복잡도 : O(n^2)
*/
for (int i = 0; i < n - 1 ; i++) { // 전체 반복 횟수는 n-1회
for (int j = 0; j < n - i - 1; j++) { // 우측 원소가 고정되면 더 이상 해당 원소는 탐색할 필요 X
// i가 1씩 증가함에 따라 (반복 횟수가 증가할 때) 탐색해야 하는 원소 수는 1씩 감소 (n - i - 1)
if (arr[j] > arr[j + 1]) {
// swap
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return Arrays.toString(arr).replaceAll("[^0-9 ]", "");
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); // buffer clear
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(solution(n, arr));
}
}
3. 삽입 정렬
package inflearn.sorting_searching;
import java.util.Arrays;
import java.util.Scanner;
public class P06_03 {
public static String solution(int n, int[] arr) {
/*
* [삽입 정렬]
* 선택 정렬과 마찬가지로 앞에서 부터 정렬해 나간다
* 다만, i가 증가하면서 j는 i-1~0까지 감소하며 순회하다가 arr[i]보다 작은 값이 발견되면 arr[j+1]에 원소를 '삽입'한다는 것이 차이점
* arr[0]까지 arr[i]보다 작은 값이 없으면 내부 for-loop 종료 후 arr[j+1(=0)]에 기존 arr[i](tmp에 유지)를 저장 - 이 경우 맨 앞에 '삽입'된다.
* 시간 복잡도 : O(n^2)
*/
for (int i = 1; i < n; i++) { // j가 i-1부터 감소하므로 i는 1부터 시작 (최초엔 2개 원소 비교)
int tmp = arr[i]; // 현재의 i 번째 원소를 저장
int j = i - 1;
for (; j > -1; j--) { // break 없이 반복 종료 시 j = -1
if (arr[j] > tmp) arr[j + 1] = arr[j]; // 한 칸 뒤로 미룸
else break; // tmp보다 작은 수가 발견되면 break
}
arr[j + 1] = tmp; // 마지막 j 위치 다음 index에 tmp를 '삽입'한다.
}
return Arrays.toString(arr).replaceAll("[^0-9 ]", "");
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); // buffer clear
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(solution(n, arr));
}
}
4. LRU (카카오 변형)
package inflearn.sorting_searching;
import java.util.Arrays;
import java.util.Scanner;
public class P06_04 {
public static String solution(int s, int n, int[] arr) {
int[] cache = new int[s];
for (int i = 0; i < n; i++) { // 작업 개수만큼 반복
// cache miss || hit 판별
int c = 0;
for (; c < s; c++) {
if (cache[c] == arr[i]) { // cache hit 시
break;
}
}
if (c == s) c--; // cache miss 시 c를 마지막 원소의 index로 옮겨줌
// c부터 0까지 cache를 뒤로 미루고 맨 앞에 arr[i]를 넣음
for (int j = c; j > 0 ; j--) {
cache[j] = cache[j - 1];
}
cache[0] = arr[i];
}
return Arrays.toString(cache).replaceAll("[^0-9 ]", "");
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int s = sc.nextInt(); // 캐시 크기
int n = sc.nextInt(); // 작업 개수
sc.nextLine(); // buffer clear
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(solution(s, n, arr));
}
}
5. 중복 확인
package inflearn.sorting_searching;
import java.util.Arrays;
import java.util.Scanner;
public class P06_05 {
public static String solution(int n, int[] arr) {
// hashmap으로 O(n)에 풀이할 수도 있음
for (int i = 1; i < n; i++) {
int tmp = arr[i];
int j = i - 1;
for (; j > -1; j--) {
if (arr[j] > tmp) arr[j + 1] = arr[j];
else if (arr[j] == tmp) return "D";
else break; // arr[j] < tmp, 중간에 삽입 수행
}
arr[j + 1] = tmp;
}
return "U";
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); // buffer clear
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(solution(n, arr));
}
}
