Algorithm/알고리즘 스터디(2021.07)
[Algorithm] 백준 sort 문제풀이
binaryJournalist
2021. 7. 29. 20:19
반응형
인프런 강의
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
일곱번째 강의에 대한 리뷰이다.
배웠던 정렬을 가지고 백준 문제를 풀었다.
1. 수 정렬하기
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
1) C++
#include <stdio.h>
int array[1001];
int main(void) {
int number, i, j, min, index, temp;
scanf("%d", &number);
for (i = 0; i < number; i++) {
scanf("%d", &array[i]);
}
for (i = 0; i < number; i++) {
min = 1001;
for (j = i; j < number; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for (i = 0; i < number; i++) {
printf("%d", array[i]);
printf("\n");
}
}
2) Python
이건 예전에 풀어놨던 풀이다.
N = int(input())
li = []
for i in range(N):
li.append(int(input()))
li = sorted(li)
for i in range(N):
print(li[i])
3) javascript
백준에서 javascript를 지원하는 건 아니지만 있다면 아마 이렇게 풀지 않았을까 싶다.
function sortNumber() {
const count = prompt();
let numbers = [];
if (count == null || count === "" ) return false;
for (var i = 0; i < Number(count); i++) {
const input = prompt();
if (input == null || input === "" ) return false;
numbers.push(Number(input));
}
numbers
.sort((a, b) => a - b)
.forEach((number) => {
console.log(number);
});
}
sortNumber();
4) Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int[] array = new int[count];
int i, j, temp;
for (i = 0; i < count; i++) {
array[i] = sc.nextInt();
}
for (i = 0; i < count; i++) {
for (j = i; j < count; j++) {
if (array[i] > array[j]) {
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
for (i = 0; i < count; i++) {
System.out.println(array[i]);
}
}
}
구글링했더니 더 좋은 방법도 있었다.
import java.util.Scanner;
import java.util.Arrays;
public class Main() {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int val : arr) {
System.out.println(val);
}
}
}
출처: https://st-lab.tistory.com/105
java.utils.Arrays 유틸리티 클래스를 이용하면 인스턴스 생성없이 숫자나 문자열도 쉽게 정렬할 수 있다. 기본값은 오름차순이다. 내림차순도 가능하나 primitive Type 의 배열의 내림차순은 불가능하다.
출처: https://ifuwanna.tistory.com/232
2. 세수정렬
https://www.acmicpc.net/problem/2752
1) C++
#include <stdio.h>
int array[3];
int main(void) {
int i, j, min, index, temp;
for (i = 0; i < 3; i++) {
scanf("%d", &array[i]);
}
for (i = 0; i < 3; i++) {
min = 1000001;
for (j = i; j < 3; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for (i = 0; i < 3; i++) {
printf("%d ", array[i]);
}
}
2) Java
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []array = new int[3];
int i, j, min, temp;
int index = 0;
for(i = 0; i < 3; i++) {
array[i] = sc.nextInt();
}
for (i = 0; i < 3; i++) {
min = 1000001;
for (j = i; j < 3; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for (i = 0; i < 3; i++) {
System.out.printf("%d ", array[i]);
}
}
}
3. 수 정렬하기
https://www.acmicpc.net/problem/2751
1) C++
#include <stdio.h>
int number, data[1000001];
void quickSort(int *data, int start, int end) {
if (start >= end) {
return;
}
int key = start;
int i = start + 1;
int j = end;
int temp;
while (i <= j) {
while(data[i] <= data[key]) {
i++;
}
while(data[j] >= data[key] && j > start) {
j--;
}
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
scanf("%d", &number);
for(int i = 0; i < number; i++) {
scanf("%d", &data[i]);
}
quickSort(data, 0, number - 1);
for (int i = 0; i < number; i++) {
printf("%d\n", data[i]);
}
}
아래는 C++ 라이브러리를 이용하여 간략히 쓴 식이다.
#include <stdio.h>
#include <algorithm>
int number, data[1000001];
int main(void) {
scanf("%d", &number);
for(int i = 0; i < number; i++) {
scanf("%d", &data[i]);
}
std::sort(data, data + number);
for (int i = 0; i < number; i++) {
printf("%d\n", data[i]);
}
return 0;
}
2) Java
위 C++ 을 Java로 바로 바꾼 식은 아래와 같다. 하지만 시간초과 걸린다.
import java.util.Scanner;
public class Main
{
private static void quickSort(int[] data, int start, int end) {
if (start >= end) {
return;
}
int key = start;
int i = start + 1;
int j = end;
int temp;
while (i <= j) {
while(i < data.length && data[i] <= data[key]) {
i++;
}
while(data[j] >= data[key] && j > start) {
j--;
}
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
} else {
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
public static void main(String[] args) {
int number;
int[] data = new int[1000001];
Scanner sc = new Scanner(System.in);
number = sc.nextInt();
for(int i = 0; i < number; i++) {
data[i] = sc.nextInt();
}
quickSort(data, 0, number - 1);
for (int i = 0; i < number; i++) {
System.out.println(data[i]);
}
}
}
Arrays.sort 를 이용해도 컴파일 에러 혹은 시간 초과가 난다.
그래서 결국 구글링해봄 (https://st-lab.tistory.com/106) <- 더 많은 방법을 보고 싶다면 이 블로그 참고
이번 경우 Arrays.sort 가 아닌 Collections.sort 를 이용한다.
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = in.nextInt();
// list 계열 중 하나를 쓰면 된다.
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
list.add(in.nextInt());
}
Collections.sort(list);
for(int value : list) {
sb.append(value).append('\n');
}
System.out.println(sb);
}
}
나는 아래 print 부분을 for 문 안에 넣어봤는데 시간 초과가 난다. (다른 컴파일러에서는 문제 없었음)
위처럼 쓴 이유가 있나보다.
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = in.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
list.add(in.nextInt());
}
Collections.sort(list);
for(int value : list) {
System.out.println(value);
}
}
}
반응형