[Algorithm] 백준 sort 문제풀이

 

인프런 강의

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

일곱번째 강의에 대한 리뷰이다.

 

 

배웠던 정렬을 가지고 백준 문제를 풀었다.

 

 

 

1. 수 정렬하기

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

 

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);
		}
	}
}