Java 정렬, 이분검색과 결정알고리즘 1
자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의
자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성
www.inflearn.com
문제 1 :
숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.
해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.
단, 선택 정렬을 이용
ex)
5
2 6 13 5 9
->
2 5 6 9 13
선택 정렬이란?
소스코드 (빠른 입출력과 StringBuilder 사용) :
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
class Main {
public String solution(int n, int[] arr) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<n-1; i++) {
int idxMin = i;
for(int j=i+1; j<n; j++) {
if (arr[j] < arr[idxMin]) idxMin = j;
}
// swap(arr[i], arr[idxMin])
int temp = arr[i];
arr[i] = arr[idxMin];
arr[idxMin] = temp;
sb.append(Integer.toString(arr[i])).append(" ");
}
sb.append(Integer.toString(arr[n-1]));
String answer = sb.toString();
return answer;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String k = br.readLine();
StringTokenizer st = new StringTokenizer(k);
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
bw.write(T.solution(n, arr));
bw.flush();
bw.close();
}
}
음.. 빨라서 좋긴 하지만 당분간은 평범하게 코드 작성해야겠다.
소스코드 :
import java.util.*;
class Main {
public int[] solution(int n, int[] arr) {
for(int i=0; i<n; i++) {
int minIdx = i;
for(int j=i+1; j<n; j++) {
if (arr[minIdx] > arr[j]) minIdx = j;
}
// swap
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
return arr;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = sc.nextInt();
}
for(int x : T.solution(n, arr)) {
System.out.print(x+" ");
}
}
}
문제 2 :
숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.
해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.
단, 버블 정렬을 이용
ex)
5
2 6 13 5 9
->
2 5 6 9 13
버블 정렬이란?
소스코드 :
import java.util.*;
class Main {
public int[] solution(int n, int[] arr) {
// n-1만큼 반복
for(int i=0; i<n-1; i++) {
// 반복할 때 마다 마지막 자리가 결정되므로 j<n-1-i
for(int j=0; j<n-1-i; j++) {
if (arr[j] > arr[j+1]) {
// swap
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
return arr;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) arr[i] = sc.nextInt();
for(int x : T.solution(n, arr)) System.out.print(x+" ");
}
}
문제 3 :
숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.
해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.
단, 삽입 정렬을 이용
ex)
5
2 6 13 5 9
->
2 5 6 9 13
삽입 정렬이란?
소스코드 :
import java.util.*;
class Main {
public int[] solution(int n, int[] arr) {
// i=1 부터 시작
for(int i=1; i<n; i++) {
int select = arr[i], j;
// i-1부터 0까지 역방향으로 진행됨
for(j=i-1; j>=0; j--) {
if (arr[j] > select) arr[j+1] = arr[j];
else break;
}
// 끝까지 돌렸거나(j=-1), arr[j]가 select보다 크지 않을 경우 j+1에 select 삽입
arr[j+1] = select;
}
return arr;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) arr[i] = sc.nextInt();
for(int x : T.solution(n, arr)) System.out.print(x+" ");
}
}