[백준 알고리즘] 백준 2750번: 수 정렬하기 / 자바 Java 8 (삽입 정렬, 버블 정렬)
🔔 문제
출처 : https://www.acmicpc.net/problem/2750
☕ Java로 풀게 된 배경 & 어려웠던 점
최근, 취업을 준비하고 있는 와중에 한 회사에서 면접을 보러오라는 연락이 왔다.
(이력서 넣은 대부분이 Java 기반 웹 개발하는 직무이다)그동안 알고리즘은 거의 파이썬으로만 풀었다.
그렇다보니, 자바를 까먹을까봐 걱정되어 그런 것도 있지만… 기술면접을 대비해서 공부를 하다보니 기본 정렬 알고리즘은 자바로 기본적인 문제를 풀면서 공부하고 넘어가면 좋을 것 같다는 생각이 들었다.구글링해서 정리를 잘 해놓으신 분들의 블로그를 찾아 개념을 이해하고, 올려놓아주신 소스 코드를 응용해서 문제를 풀어보았다.
알고리즘을 자바로 (거의) 처음 풀어보기도 했고 (거기에다가 하필! 백준)
자바로 웹 개발 공부하다가~ 파이썬으로 알고리즘 풀면서 파이썬이 다시 익숙해질 쯤… 갑자기! 다시 자바를 하니 헷갈리는 부분과 어색한 부분이 많았던 것 같다.어쨋든, 간단한 정렬 문제이지만 자바로 거품 정렬과 삽입 정렬 알고리즘을 활용해서 문제를 풀어보니 기본적인 정렬 알고리즘의 개념과 매커니즘이 조금 정리가 되는 듯 하다 💪
🔊 참고하면서 공부한 블로그 링크 : 선택 정렬(Selection Sort) | 거품 정렬(Bubble Sort) | 삽입 정렬(Insertion Sort)
(P.S : https://st-lab.tistory.com/ 님 좋은 자료 및 정리 감사합니다 😊)
🔐 해결 (소스 코드)
1. 거품 정렬(버블 정렬) 알고리즘 활용
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = sc.nextInt();
}
sc.close(); // n에 지정한 수 만큼 반복해서 리스트에다 값을 넣고 close
// round는 배열 크기 - 1 만큼 진행됨
for(int i=1; i<n; i++) {
// 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교한다
for(int j=0; j < n-i; j++) {
// 현재 원소가 다음 원소보다 클 경우 : 서로 원소의 위치를 교환한다
if(arr[j] > arr[j+1]) {
// swap
swap(arr, j, j+1);
}
}
}
for (int k=0; k<n; k++) {
System.out.println(arr[k]);
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
// swap 해주는 기능 따로 지정
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2. 삽입 정렬 알고리즘 활용
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = sc.nextInt();
}
sc.close(); // n에 지정한 수 만큼 반복해서 리스트에다 값을 넣고 close
for(int i=1; i<n; i++) {
// 타겟이 되는 인덱스의 넘버
int target = arr[i];
int j = i - 1;
// 타겟이 이전 원소보다 크기 전까지 반복
while(j >= 0 && target < arr[j]) {
arr[j+1] = arr[j]; // 이전 원소를 한 칸씩 뒤로 미룬다
j--;
}
arr[j+1] = target;
/*
* 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
* 타겟 원소는 j번째 원소 뒤에 와야한다.
* 그러므로 타겟은 j+1 에 위치하게 된다.
*/
}
for (int k=0; k<n; k++) {
System.out.println(arr[k]);
}
}
}
Leave a comment