문제
온라인 저지 회원 N명의 나이와 이름이 주어질 때, 나이 오름차순으로 정렬하되 나이가 같으면 먼저 가입한 순서(입력 순서)를 유지해 출력하는 문제다.
입력
- 첫째 줄: N
- 이후 N개 줄: 나이와 이름
출력
나이 오름차순, 동일 나이면 가입 순서로 정렬된 회원 목록
예제
| 입력 | 출력 |
|---|---|
3 21 Junkyu 21 Dohyun 20 Sunyoung | 20 Sunyoung 21 Junkyu 21 Dohyun |
풀이
나이를 기준으로 정렬하되, 같은 나이일 때 입력 순서를 보존해야 한다. Java의 Arrays.sort는 안정 정렬(stable sort)이므로, 나이만 비교하는 Comparator를 사용하면 같은 나이 내에서 원래 순서가 유지된다.
- N을 입력받고
String[N][2]배열에 나이(index 0)와 이름(index 1)을 저장한다. Arrays.sort에 나이를 정수로 파싱해 비교하는 Comparator를 전달한다.- 정렬 결과를 StringBuilder로 모아 한 번에 출력한다.
핵심 아이디어: Java의 Arrays.sort는 객체 배열에 대해 안정 정렬(TimSort)을 보장한다. 동일 나이 원소의 상대 순서가 그대로 유지되므로 별도의 인덱스 처리 없이 입력 순서를 보존할 수 있다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Day05BOJ10814나이순정렬 { // 10814 나이순 이름 정렬, 나이가 같으면 등록순
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
String[][] nameArr = new String[N][2];
for (int t = 0; t < N; t++) {
st = new StringTokenizer(br.readLine());
nameArr[t][0] = st.nextToken();
nameArr[t][1] = st.nextToken();
}
// for (int i = N - 1; i >= 0; i--) {
// for (int j = 0; j < i; j++) {
// if (Integer.parseInt(nameArr[j][0]) > Integer.parseInt(nameArr[j + 1][0])) {
// String[] temp = nameArr[j];
// nameArr[j] = nameArr[j + 1];
// nameArr[j + 1] = temp;
// }
// }
// } // 아직 우리가 배운 정렬로는 백준 문제를 풀 수 없습니다..
Arrays.sort(nameArr, new Comparator<String[]>() {
@Override
public int compare(String[] nameArr1, String[] nameArr2) {
return Integer.parseInt(nameArr1[0]) - Integer.parseInt(nameArr2[0]);
}
});
for (int i = 0; i < N; i++)
sb.append(nameArr[i][0]).append(" ").append(nameArr[i][1]).append("\n");
System.out.println(sb);
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)