백준 10814번 나이순 정렬 [Queue] :: 마이구미

이번 글은 백준 알고리즘 10814번 "나이순 정렬"에 대해 알아볼 것이다.

본인은 다르게 풀었지만 다른 사람이 푼 것을 보고 이 글의 메인을 정했다.

PriorityQueue 우선순위 큐를 통해 문제를 해결해보자.

Github - https://github.com/hotehrud/acmicpc

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이 때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

큐는 모두 알다고 가정한다.

큐에는 원형 큐, 우선순위 큐, 덱큐가 있다.

PriorityQueue 이녀석은 해석하면 알겠지만 우선순위 큐이다.

우선순위 큐는 말 그대로 우선순위가 높은 데이터를 먼저 꺼내온다.

이번 문제는 이해하기에 간단하다. 

정렬만 잘해주면 된다.

나이순으로 정렬하고, 나이 같으면 먼저 온 사람이 먼저.

나 같은 경우는 이렇게 생각했다.

순서를 보장해주는 ArrayList를 써서 나이순으로만 정렬하면 끝 아닌가?

끝 맞다...

하지만 여기선 우선순위 큐를 통하여 풀 것이다. ( ArrayList 소스도 하단에 올려놓았다 )

생성하는 법은 크게 두가지로 볼 수 있다.

아래와 같이 생성자를 통해서나, 크기와 Comparator를 함께 전달하여 생성하는 방법이 있다.

PriorityQueue<Member> q = new PriorityQueue<Member>();
PriorityQueue<> q = new PriorityQueue<>(size, Comparator<> comparator);

그렇다면 이제 문제를 풀어보자.

우선순위 큐를 어떻게 만드냐에 따라 쉽게 해결 여부를 좌우한다.

static class Member{
        int age;
        String name;
         
        Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }

PriorityQueue<Member> q =
                new PriorityQueue<Member>(100000, new Comparator<Member>() {
                    @Override
                    public int compare(Member m1, Member m2) {
                        if(m1.age < m2.age) {
                            return -1;
                        } else if (m1.age > m2.age) {
                            return 1;
                        }
                        return 0;
                    }
                });

우선순위 큐를 생성할 때 compare 메소드를 오버라이딩 하였다.

compare 메소드는 리턴 값이 음수일 경우는 우선순위가 올라간다.

나도 이렇게 하면 끝이겠구나 생각했다.

하지만 순서를 보장해주지 않았다.

그래서 순서를 가지고 있을 수 있는 고유 변수를 하나 추가해주어야했다.

Member 클래스에 변수를 하나 추가해주면서 해결하였다.

PriorityQueue<Member> q =
                new PriorityQueue<Member>(100000, new Comparator<Member>() {
                    @Override
                    public int compare(Member m1, Member m2) {
                        if(m1.age < m2.age) {
                            return -1;
                        } else if (m1.age > m2.age) {
                            return 1;
                        }else{
                            return m1.uid - m2.uid; 
                        }
                    }
                });

PriorityQueue 클래스 기본적인 사용법만 숙지한다면 어렵지 않다.

어려운 기술을 쓴 것도 아니고, 소스가 복잡한 것도 아니고... 설명할 건 없다.

문제 해결법은 "어떻게 효율적이게 정렬을 할 것인가" 이기 때문이다.

이번 글에서는 PriorityQueue 녀석을 알고 가길 바라는 게 크다.

PriorityQueue 소스

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

public class Main {
    
    static class Member{
        int uid;
        int age;
        String name;
         
        Member(int uid, int age, String name) {
            this.uid = uid;
            this.age = age;
            this.name = name;
        }
    }
     
    public static void main(String[] args) throws IOException {
    	PriorityQueue<Member> q1 = new PriorityQueue<Member>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Member> q =
                new PriorityQueue<Member>(100000, new Comparator<Member>() {
                    @Override
                    public int compare(Member m1, Member m2) {
                        if(m1.age < m2.age) {
                            return -1;
                        } else if (m1.age > m2.age) {
                            return 1;
                        }else{
                            return m1.uid - m2.uid; 
                        }
                    }
                });
         
        int n = Integer.parseInt(br.readLine());
         
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            q.add( new Member(i, Integer.parseInt(st.nextToken()), st.nextToken()) );
        }
         
        while(!q.isEmpty()) {
            Member m = q.poll();
             
            System.out.println(m.age + " " + m.name);
        }
 
    }
}

ArrayList 소스

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    static class Dic
    {
        int key;
        String value;
           
        Dic(int key, String value) {
            this.key = key;
            this.value = value;
        }
         
        @Override
        public String toString() {
            // TODO Auto-generated method stub
            StringBuilder str = new StringBuilder();
            str.append(key);
            str.append(value);
       
            return str.toString();
        }
         
    }
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
   
        List<Dic> dic = new ArrayList<Dic>();
           
        int num = sc.nextInt();
        sc.nextLine();
        for(int i=0;i<num;i++)
        {
            int key = sc.nextInt();
            String value = sc.nextLine();
            dic.add(getCreateDic(key, value));
        }
        Collections.sort(dic, new Comparator<Dic>() {
 
            @Override
            public int compare(Dic o1, Dic o2) {
                // TODO Auto-generated method stub
                return o1.key - o2.key;
            }
             
        });
        for (Dic temp : dic) {
            System.out.println(temp);
        }
           
    }
     
    static Dic getCreateDic(int key, String value)
    {
        Dic dic = new Dic(key, value);
           
        return dic;
    }
  
}