[JAVA] 백준-10814 나이순 정렬

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

---

 

---

3가지의 풀이 방법을 성능 순서로 작성하겠다.

 

1. String[ ][ ] + Arrays.sort( )

나이와 입력을 2차원 String 배열에 입력받고 Arrays.sort( )를 이용하여 정렬한 뒤 출력하는 방법이다. 

람다식으로 Comparator인터페이스 compare를 구현하여 2차원 배열이 정렬되도록 하였다.

다만 출력를 반복적으로 하기 때문에 성능이 좋지 않다.

난생처음 보는 시간을 보고 충격을...

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		String[][] member=new String[n][2];
		for(int i=0;i<n;i++) {
			member[i]=br.readLine().split(" "); //나이와 이름 입력
		}
	
		Arrays.sort(member,(arr1, arr2) ->Integer.compare(Integer.parseInt(arr1[0]), Integer.parseInt(arr2[0])));
		for(int i=0;i<n;i++) { //출력
			System.out.println(member[i][0]+" "+member[i][1]);
		}
	}
}

---

2. String[ ][ ] + Arrays.sort( ) + StringBuilder

위의 코드와 알고리즘은 동일하다.

다만 출력하기 전에 StringBuilder를 이용하여 입력값을 모은 다음 한 번에 출력하기에 성능이 많이 좋아진다.

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		String[][] member=new String[n][2];
		for(int i=0;i<n;i++) {
			member[i]=br.readLine().split(" ");
		}
	
		Arrays.sort(member,(arr1, arr2) ->Integer.compare(Integer.parseInt(arr1[0]), Integer.parseInt(arr2[0])));
		StringBuilder sb= new StringBuilder();
		for(int i=0;i<n;i++) {
			sb.append(member[i][0]).append(' ').append(member[i][1]).append('\n');
		}
		System.out.println(sb);
	}
}

 

---

3.   Counting sort +StringBuilder

사실 굳이 Arrays.sort를 사용하지 않고 풀수 있다.

나이의 값의 범위가 크지 않기 때문에 Counting sort의 형태를 사용하면 입력과 동시에 정렬이 가능하다.

Counting sort를 모르는 분들을 위해 아주 간단하게 설명하자면 입력받는 범위만큼 배열을 만들고 그 값에 해당하는 index를 1씩 증가시키고 이후 index의 값만큼 반복하여 출력하는 방법이다. 여기서 stable하게 정렬하고자 하면 좀 더 여러 단계를 거쳐야 하는데 여백이 부족해서....

하여튼 입력과 동시에 정렬을 하기때문에 성능 첫 번째 것과 비교화면 굉장히 좋아진다.

 

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		StringBuilder[] sb= new StringBuilder[201]; //값을 입력받을 StringBuilder 선언
		for (int i = 0; i < sb.length; i++) {
			sb[i] = new StringBuilder();
		}
		for(int i=0;i<n;i++) { //Counting sort
			StringTokenizer st=new StringTokenizer(br.readLine()," ");
			int age=Integer.parseInt(st.nextToken());
			sb[age].append(age).append(' ').append(st.nextToken()).append('\n');
		}
		StringBuilder tmp= new StringBuilder();
		for(int i=0;i<sb.length;i++) { //한번에 출력하기위해 StringBuilder 사용
			tmp.append(sb[i]);
		}
		System.out.println(tmp.toString());
	}
}