[백준] 나이순 정렬
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 회원 수
Map<Integer, String> hashMap = new HashMap<>(); // 회원을 저장할 해시맵
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int key = Integer.parseInt(st.nextToken());
String value = st.nextToken();
hashMap.put(key, value);
}
List<Integer> keySet = new ArrayList<>(hashMap.keySet()); // 해시맵을 ArrayList로 변환
Collections.sort(keySet); // ArrayList를 정렬
// 출력
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
br.close();
}
}나는 우선 이렇게 풀었다.
회원 수를 입력받고, 회원을 저장할 hashmap을 선언하였다.
문제를 보면 key와 value로 이루어져 있는 것 같아 딕셔너리를 사용하기로 했다.
그리고나서 for문을 순회하며 key값과 value값을 입력받고 hashmap에 저장한다.
hashmap을 ArrayList로 변환을 하고, 변환된 ArrayList를 정렬한다.
마지막으로 출력까지 했다.
하지만 내가 푼 코드에는 몇가지 문제점이 존재했다.
1. HashMap의 부적절한 사용:
- HashMap은 키가 중복될 수 없다. 만약 여러 사람이 같은 나이라면, 마지막 입력된 사람만 저장된다.
- 또한 HashMap은 입력 순서를 보존하지 않는다.
2. 정렬 로직의 문제:
- 문제는 "나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서"로 정렬을 요구한다.
- 현재 코드는 keySet만 정렬하고 있으며, 출력 부분에서는 정렬된 keySet을 사용하지 않고 있다.
3. 가입 순서 정보 손실:
- 현재 코드는 가입 순서를 저장하지 않아서 "나이가 같으면 먼저 가입한 사람이 앞에 오는" 조건을 충족할 수 없다.
그래서 다음과 같이 해결했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 나이, 이름, 가입순서를 모두 저장할 리스트
List<Member> members = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int age = Integer.parseInt(st.nextToken());
String name = st.nextToken();
members.add(new Member(age, name, i)); // 가입순서(i)도 함께 저장
}
// 나이 순으로 정렬하고, 나이가 같으면 가입순서로 정렬
Collections.sort(members, new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
if (o1.age == o2.age) {
return o1.order - o2.order; // 나이가 같으면 가입 순서로
}
return o1.age - o2.age; // 나이 오름차순
}
});
// 결과 출력
for (Member member : members) {
System.out.println(member.age + " " + member.name);
}
br.close();
}
// 회원 정보를 담을 클래스
static class Member {
int age;
String name;
int order; // 가입 순서
public Member(int age, String name, int order) {
this.age = age;
this.name = name;
this.order = order;
}
}
}우선 회원 수를 저장할 n을 똑같이 입력받는다.
그리고 내 코드와의 가장 큰 차이점으로는 이 코드에선 가입순서도 리스트에 저장한다.
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int age = Integer.parseInt(st.nextToken());
String name = st.nextToken();
members.add(new Member(age, name, i)); // 가입순서(i)도 함께 저장
}for문을 n까지 순회하며 가입순서인 i를 포함하여 member 객체를 생성해서 리스트에 저장한다.
// 나이 순으로 정렬하고, 나이가 같으면 가입순서로 정렬
Collections.sort(members, new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
if (o1.age == o2.age) {
return o1.order - o2.order; // 나이가 같으면 가입 순서로
}
return o1.age - o2.age; // 나이 오름차순
}
});그리고 나서 sort() 메서드를 이용하여 나이순으로 정렬하고, 나이가 같다면 가입 순서로 정렬하고, 그렇지 않다면 나이를 오름차순으로 정렬하게 된다.
for (Member member : members) {
System.out.println(member.age + " " + member.name);
}마지막으로 결과를 출력하면 된다.
내가 이 코드에서 가장 궁금한 부분은 Collections.sort()부분이다.
음수를 return했을 때, o1이 o2보다 앞에 와야하고,
양수를 return했을 때, o1이 o2보다 뒤에 와야한다.
이 부분이 이해가 되지 않아 Java에서 Comparator의 정렬 원리에 관한 개념을 찾아보았다.Java의 compare 메서드에서 리턴값과 정렬 순서의 관계는 "수학적 비교"의 개념을 따른다.
1. 음수 반환 (o1이 o2보다 앞에 오는 이유)compare 메서드가 음수를 반환하면, 이는 "o1이 o2보다 작다"라는 의미이다. 정렬 알고리즘은 "작은 것이 먼저" 원칙에 따라 o1을 o2보다 앞에 배치한다.
예를 들어, 숫자 정렬에서:3과 5를 비교할 때: 3-5 = -2 (음수)
정렬 알고리즘: "3이 5보다 작으니 3을 먼저 놓자"
2. 양수 반환 (o1이 o2보다 뒤에 오는 이유)compare 메서드가 양수를 반환하면, 이는 "o1이 o2보다 크다"라는 의미이다. 정렬 알고리즘은 "큰 것이 나중에" 원칙에 따라 o1을 o2보다 뒤에 배치한다.
예를 들어, 숫자 정렬에서:8과 4를 비교할 때: 8-4 = 4 (양수)
정렬 알고리즘: "8이 4보다 크니 8을 나중에 놓자"
이와 같은 개념을 난 전혀 모르고 있었다.
if (o1.age == o2.age) {
return o1.order - o2.order; // 나이 같으면 가입 순서 오름차순
}
return o1.age - o2.age; // 나이 오름차순if (o1.age == o2.age) {
return o2.order - o1.order; // 나이 같으면 가입 순서 내림차순
}
return o2.age - o1.age; // 나이 내림차순추가로 이 두 코드가 완전히 반대의 정렬 개념을 갖는다는 사실도 알게 되었다.
예를 들어보겠다.
- o1.age - o2.age
- o1.age=20, o2.age=30 → 결과: -10(음수) → o1이 앞에 옴
- o2.age - o1.age
- o1.age=20, o2.age=30 → 결과: 10(양수) → o1이 뒤에 옴
이런 결과가 도출된다는 사실을 처음 알게 되었다.