[Java] 백준 10814번 : 나이순 정렬

문제

해결 방법

시간제한 3초라서 selection sort로 index 비교하며 정렬해주었는데, 시간 초과 뜸..
그래서 나이 입력조건이 1~200 인것을 확인하고, 내가 싫어하는 Counting sort를 적용하여 해결하였다 !

Counting sort가 뭔데 ?

범위 만큼의 배열을 선언하여 그 값에 해당하는 index를 1씩 증가시키며 저장하고
index의 값만큼 반복하여 출력하는 sorting 기법이다.
메모리를 범위만큼 할당받아야 하기 때문에, 범위가 좁은 경우에만 사용 가능하며, O(n)의 시간 복잡도를 가진다 ~
Input의 개수가 많고 범위가 좁은 곳에 사용하기 적합하다 !

ex) 1억개의 input, 범위는 [-100, 100] 을 정렬해보자
1. 201 크기의 배열을 선언한다.
2. 입력 받은 값을 index로 참조하여 배열의 값을 1 증가시킨다. (arr[input]++)
3. 배열을 돌면서 0이 아닌 값에 대해 해당 숫자만큼 반복하여 출력한다.

코드

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

/**
 * <pre>
 * 백준 10814. 나이순 정렬
 * 1. N과 나이 이름을 입력받아 split 후 각각의 int, String 배열에 저장
 * 2. 나이 배열을 돌면서 나이순으로 정렬, 이 때 String 배열도 index를 변경해줘야 함
 * </pre>
 * 
 * @author 세진
 *
 */
public class Main {

	/**
	 * @param args Nooo
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1. 사용자 입력 객체 생성
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 2. n 입력 후 int로 parsing하여 저장
		int n = Integer.valueOf(br.readLine());

		// 3. 입력받은 나이를 저장하기 위한 변수와 Counting sort를 하기 위한 StringBuilder 배열 선언 (나이 범위가 0 ~ 200이기 때문에 201의 크기를 가짐)
		int curAges = 0;
		StringBuilder[] sb = new StringBuilder[201];
		
		// 4. for구문 돌면서 나이와 이름을 입력받고, 만약 해당 StringBuilder 배열이 null값이면 생성자로 선언 후 "나이 이름\n"의 형식으로 append
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			curAges = Integer.valueOf(st.nextToken());
			
			if (sb[curAges] == null) {
				sb[curAges] = new StringBuilder();
			}
			
			sb[curAges].append(curAges);
			sb[curAges].append(" ");
			sb[curAges].append(st.nextToken());
			sb[curAges].append("\n");
			
		}

		// 5. StringBuilder 크기만큼 반복하며 null이 아닌 객체에 대해 toString + 마지막 공백 제거를 위한 trim 후 출력
		for (int i = 0; i < 201; i++) {
			
			if (sb[i] == null) continue;
			
			System.out.println(sb[i].toString().trim());
			
		}
		
	}

}

결과 / 느낀 점

처음 통과했을 때에는, Counting sort로 나이를 정렬하고 배열을 한번 더 돌면서 String 값을 출력했다.
그러니까 1272 ms라는 충격적인(?) 결과를 보고,,
StringBuilder를 사용하여 그 index에 바로바로 나이 이름을 추가하는 식으로 개선했다 !
갈 길이 멀다 ,,, 화이팅