문제 설명
온라인 저지 회원들의 정보가 가입한 순서대로 주어진다.
각 회원 정보는 다음과 같다.
- 나이
- 이름
이 회원들을 다음 기준으로 정렬해야 한다.
- 나이가 증가하는 순
- 나이가 같으면 먼저 가입한 사람 순
즉, 단순히 나이만 정렬하는 것이 아니라
같은 나이일 때 입력 순서를 유지해야 하는 문제이다.
입력
첫째 줄에 회원 수 N이 주어진다.
1 ≤ N ≤ 100000다음 줄부터 N개의 줄에 걸쳐
나이 이름형태로 주어진다.
조건
나이: 1 이상 200 이하
이름: 알파벳 대소문자, 길이 100 이하출력
정렬된 결과를 한 줄에 한 명씩
나이 이름형식으로 출력한다.
입력 예시
3
21 Junkyu
21 Dohyun
20 Sunyoung출력 예시
20 Sunyoung
21 Junkyu
21 Dohyun문제 해결 아이디어
이 문제의 핵심은 다음이다.
나이 오름차순 정렬
+
같은 나이면 입력 순서 유지즉, 안정 정렬(stable sort) 개념이 중요한 문제이다.
내가 작성한 코드
나는 Member 클래스를 만들어
- 이름
- 나이
- 입력 순서
를 함께 저장한 뒤 정렬했다.
코드
import java.util.*;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<Member> member = new ArrayList<>();
sc.nextLine();
for(int i = 0; i < N; i++) {
String[] input = sc.nextLine().split(" ");
member.add(new Member(input[1], Integer.parseInt(input[0]), i));
}
member.sort(new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
if(o1.age == o2.age)
return o1.count - o2.count;
return o1.age - o2.age;
}
});
for(Member m : member)
System.out.println(m.age + " " + m.name);
}
}
class Member {
String name;
int age;
int count;
public Member(String name, int age, int count) {
this.name = name;
this.age = age;
this.count = count;
}
}강의 코드
강의에서는 String[][] 배열에 나이와 이름을 저장한 뒤
나이만 기준으로 정렬했다.
코드
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[][] members = new String[N][2];
for (int i = 0; i < N; i++) {
members[i][0] = sc.next();
members[i][1] = sc.next();
}
Arrays.sort(members, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
}
});
for (int i = 0; i < N; i++)
System.out.println(members[i][0] + " " + members[i][1]);
}
}내 코드 vs 강의 코드 비교
1. 데이터 저장 방식
내 코드
Member 클래스 사용- name
- age
- count(입력 순서)
를 객체로 관리했다.
강의 코드
String[][] 배열 사용members[i][0]= 나이members[i][1]= 이름
형태로 저장했다.
2. 같은 나이 처리 방식
내 코드
같은 나이일 때 직접 입력 순서를 비교했다.
if(o1.age == o2.age)
return o1.count - o2.count;즉,
명시적으로 가입 순서를 비교한 것이다.
강의 코드
강의 코드는 나이만 비교했다.
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);그런데도 정답이 되는 이유는
Java의 Arrays.sort(Object[])가 안정 정렬이기 때문이다.
즉,
같은 나이면 기존 입력 순서를 자동 유지한다.
3. 핵심 차이
| 항목 | 내 코드 | 강의 코드 |
|---|---|---|
| 입력 순서 처리 | count 필드로 직접 관리 | 안정 정렬에 맡김 |
| 자료구조 | 클래스 객체 | 2차원 문자열 배열 |
| 가독성 | 의미가 명확함 | 코드가 짧음 |
4. 어떤 방식이 더 좋은가
내 코드 장점
- 문제 조건이 코드에 명확하게 드러남
- 같은 나이일 때 왜 이런 순서가 나오는지 바로 이해 가능
강의 코드 장점
- 코드가 짧고 간단함
- Java 정렬의 안정성을 활용할 수 있음
즉,
내 코드 = 조건을 직접 구현
강의 코드 = 언어 특성을 활용하는 차이가 있다.
커스텀 정렬 정리
이 문제도 결국 커스텀 정렬 문제이다.
정렬 기준은
- 나이 오름차순
- 같으면 가입 순
이다.
Comparator 기본 형태
new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
...
}
}compare 반환값 의미
음수 → o1이 앞
0 → 순서 유지
양수 → o2가 앞내 코드의 compare
if(o1.age == o2.age)
return o1.count - o2.count;
return o1.age - o2.age;의미는 다음과 같다.
-
나이가 다르면
→ 나이 오름차순 -
나이가 같으면
→ 입력 순서(count) 오름차순
안정 정렬(stable sort)
이 문제에서 가장 중요한 개념 중 하나가 안정 정렬이다.
안정 정렬이란
정렬 기준이 같은 원소들의 기존 순서를 유지하는 정렬을 의미한다.
강의 코드가 나이만 비교해도 정답인 이유가 바로 이것이다.
즉, 입력이 이미 가입 순서대로 들어오므로
같은 나이끼리는 원래 순서 유지가 자동으로 된다.
시간 복잡도
정렬이 핵심이므로 시간 복잡도는
O(N log N)이다.
입력 크기가 최대 100000이므로
이 정도가 적절하다.
정리
이 문제는 단순한 정렬 문제가 아니라
같은 값일 때 기존 순서를 유지해야 하는 문제였다.
내 코드는 입력 순서를 직접 count로 저장해서 처리했고,
강의 코드는 Java의 안정 정렬 특성을 이용해서 더 간단하게 해결했다.
핵심 차이는 다음과 같다.
내 코드 → 가입 순서를 직접 비교
강의 코드 → 안정 정렬을 활용이 문제를 통해 정리할 수 있는 핵심 개념은 다음과 같다.
- 커스텀 정렬
- Comparator 사용법
- 안정 정렬(stable sort)
- 같은 값일 때 기존 순서 유지
즉, 이 문제는
정렬 기준뿐 아니라 안정 정렬의 개념까지 이해하고 있어야 하는 대표적인 문제라고 볼 수 있다.
