백준 10814 나이순 정렬(JAVA)

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

10814번: 나이순 정렬

 

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BJ_10814_나이순정렬 {
    public static class person{
        int age;
        String name;
        int order;

        public person(int age, String name, int order){
            this.age = age;
            this.name = name;
            this.order = order;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<person> pq = new PriorityQueue<>(new Comparator<person>() {
            @Override
            public int compare(person o1, person o2) {
                if(o1.age == o2.age)
                    return o1.order - o2.order;
                else
                    return o1.age - o2.age;
            }
        });
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            String name = st.nextToken();

            pq.offer(new person(num, name, i));
        }
        for(int i=0; i<n; i++){
            person person = pq.poll();
            System.out.println(person.age + " " + person.name);
        }

    }
}
/*
age 순서대로 정렬할때 age가 같을때 먼저 넣는다고 앞선순서에 정렬되는 것이 아니다.
우선순위큐의 내부구조는 힙인데 따로 지정해주지 않으면 섞일 수도 있기때문에
age가 같다면 들어온 애들에 넘버를 부여해서 그 순서대로 정렬을 시켜줘야 한다.
 */

priority queue를 사용했는데, heap 정렬이라서 중간에 섞일 수 있다는 점만 유의한다면 쉽게 풀 수 있다.