알고리즘 유형 정리

정렬

정렬문제는 알고리즘 문제에서 많은 양과 다양한 유형이 존재하는 분류로서 코테 난이도 중에서 조금 쉬운 유형에 속하지만 기본적인 유형들에 대한 학습이 안되어 있으면 난항을 겪기 쉽다. Arrays.sort(), Collections.sort() 등 현재 존재하는 다양한 sort 라이브러리들이 존재하여 기본적인 정렬은 가능하지만 조금 더 특수한 케이스의 정렬을 요하는 문제에서는 이에 대한 응용 능력이 필요로해진다.

문제풀이

  1. 문제
    N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오

  2. 입력
    첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

  3. 출력
    첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

  4. 예제입력 : 10
    5
    2
    3
    1
    4
    2
    3
    5
    1
    7

  5. 예제출력: 1
    1
    2
    2
    3
    3
    4
    5
    5
    7



아래 2가지 방식으로 문제풀이를 진행하였다.


sort 라이브러리 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 백준10989_수정렬 {

	static BufferedReader reader;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		reader = new BufferedReader( new InputStreamReader(System.in));
		int N= Integer.parseInt(reader.readLine());
		solution2(N);

	public static void solution2(int N) throws NumberFormatException, IOException {
		int[] arr = new int[N];
		for(int i=0; i<N ; i++) {
			int number = Integer.parseInt(reader.readLine());
			arr[i] = number;
		}
		reader.close();
		Arrays.sort(arr);
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			sb.append(arr[i]).append("\n");
		}
		System.out.println(sb);
	}
}


배열 idx에 직접 저장방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 백준10989_수정렬 {

	static BufferedReader reader;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		reader = new BufferedReader( new InputStreamReader(System.in));
		int N= Integer.parseInt(reader.readLine());
		int[] arr =new int[10001];
		
		for(int i=0; i<N ; i++) {
			int number = Integer.parseInt(reader.readLine());
			arr[number] += 1;
		}
		reader.close();
	 	StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<10001 ; i++) {
			if(arr[i] !=0) {
				for(int j=0; j< arr[i] ; j++) {
					sb.append(i).append("\n");
				}
			}
		}
		System.out.println(sb);
	}
}


해설

이 문제는 사실 구현관점에서는 요구하는 내용이 크게 어렵지 않다. 단순히 입력 받은값을 정렬하라는 문제이다. 하지만 입력의 양이 꽤 많고, 시간과 메모리 제한을 꼼꼼하게 제시한것을 보아하니 시간,메모리 효율성에 대해 묻는 문제임을 알 수 있다. 이 부분은 알고리즘 로직에 대해 묻는 문제라기 보다는 라이브러리 사용에 대해 더 효율적인 라이브러리를 상식으로 공부하는데에 의의를 둔다.

이 문제 풀이의 가장 핵심은 Scanner 객체를 사용하지 않고 푸는 것이다. 처음에는 단순히 Scanner를 이용하여 풀었지만 시간초과가 발생하였다. 이는 Scanner을 통한 입력과 System.print.out에 대한 출력에 대한 실제 시간이 크게 소요된다는것을 의미하는 바이다.

따라서 해당 기능들 대신하여 BufferedReader와 InputStreamReader을 이용하여 입력값을 받았고,

BufferedReader reader = new BufferedReader( new InputStreamReader(System.in));

StringBuilder을 통해 출력값을 모두 저장한다음 한번의 print 출력으로만 출력하게끔 라이브러리 사용을 변경해주었다.

StringBuilder sb = new StringBuilder();

사실 이 부분만 이렇게 변경하면 위의 첫번째 방식과 두번째 방식은 모두 통과가 된다 각각 2412ms, 1480ms 시간의 소요로 패스하였다. 물론 sort()를 사용하는것은 시간이 더 크게 소요되므로 두번째 풀이 방식이 더 적절하지만 sort()까지도 패스를 시켜주는 문제였다.

sort를 사용하게 되면 배열의 크기가 클수록 시간이 크게 증가하기 때문에 배열의 크기가 클때는 시간 효율성 부분에서는 좋은 코드가 아니다. 따라서 배열의 탐색을 가장 빠르게 할 수 있는 인덱스 직접 접근 방식을 사용해야하고 그래서 두번째 방법에서 보는거와 같이 각 숫자들을 고유의 배열 주소로 사용하고 몇번 반복되었는지를 값으로 구분하여 arr 의 배열을 1부터 10001 까지 돌면서 결과를 출력하는 구문으로 바꿔 풀었다.