[백준] no10814: 나이순 정렬

문제

: 입력받은 나이 순으로 정렬

: 만약 같은 나이면 입력된 시간순으로 정렬

 

문제 링크 : https://www.acmicpc.net/problem/10814

---

원리

Comparator 클래스 사용 ( with stream )

Arrays.sort(arr, (o1, o2) -> {
	if(o1[0] == o2[0]){
    	return Integer.compare(o1[1],o2[1]);
    else{
    	return Integer.compare(o1[0],o2[0]);
    }
});

---

풀이방법

1. LinkedHashMap 이용 

 

2. LinkedMultiValueMap 이용

: 키값의 중복이 가능하나, Apache Commons에 있는 서드파티 기능이라서 JDK만 있으면 쓸 수 없음.

* 필요시 아래 링크에서 라이브러리 설치로 사용 가능

* 아파치 commons - Collection

https://search.maven.org/artifact/org.apache.commons/commons-collections4/4.4/jar

 

* 그 외 아파치 commons 다운로드 링크

https://commons.apache.org/

 

* 관련 설명 

https://118k.tistory.com/778

 

3. Matrix + Comparator 조합

 

---

나의 코드

1. LinkedHashMap사용 [ 로컬에서는 성공 했으나, 백준에서는 틀림 ]

: 우선 값을 LinkedHashMap에 저장. 이때, 나이의 중복을 허용하기 위해 나이를 Value에 입력 map.put(이름, 나이)

: Sort를 위해 LinkedList에 LinkedHashMap으로 저장한 값을 입력

: 각 요소의 Value(나이)를 비교하여 Sort

import java.io.*;
import java.util.*;

public class no10814 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

        for(int i=0; i<T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            Integer value = Integer.valueOf(st.nextToken());
            String key = st.nextToken();
            map.put(key, value);
        }

        Map<String, Integer> result = sortMapByKey(map);

        for (Map.Entry<String, Integer> entry : result.entrySet()) {
            bw.write(""+entry.getValue()+" "+entry.getKey()+"\n");
        }

        bw.close();
    }

    private static LinkedHashMap<String, Integer> sortMapByKey(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> entries = new LinkedList<>(map.entrySet());
        Collections.sort(entries, (a, b) -> a.getValue().compareTo(b.getValue()));
        LinkedHashMap<String, Integer> result = new LinkedHashMap<>();
        for(Map.Entry<String, Integer> entry : entries) {
            result.put(entry.getKey(), entry.getValue());
        }
        return result;
    }
}

 

2. LinkedHashMap ver2 [ 로컬에서는 성공 했으나, 백준에서는 틀림 ]

: 혹시 같은 이름의 회원이 있어서 문제가 되나 싶어서 키 값을 '나이 이름'형식으로 진행했으나 역시 백준에서만 실패

import java.io.*;
import java.util.*;

public class no10814 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

        for(int i=0; i<T ; i++) {
            String key = br.readLine();
            StringTokenizer st = new StringTokenizer(key, " ");
            Integer value = Integer.valueOf(st.nextToken());
            map.put(key, value);
        }

        List<Map.Entry<String, Integer>> result = sortMapByKey(map);

        for (Map.Entry<String, Integer> entry : result) {
            bw.write(entry.getKey()+"\n");
        }

        bw.close();
    }

    private static List<Map.Entry<String, Integer>> sortMapByKey(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> entries = new LinkedList<>(map.entrySet());
        Collections.sort(entries, (a, b) -> a.getValue().compareTo(b.getValue()));

        return entries;
    }
}

 

3. Matrix(String 2차원 배열)과 Comparator를 이용한 방법 [ 메모리 시간 많이 소모하나, 백준은 통과 ]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class no10814 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        String[][] matrix = new String[T][2];

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            matrix[i][0] = st.nextToken();
            matrix[i][1] = st.nextToken();
        }
        Arrays.sort(matrix, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(Integer.parseInt(o1[1]), Integer.parseInt(o2[1]));
            } else {
                return Integer.compare(Integer.parseInt(o1[0]), Integer.parseInt(o2[0]));
            }
        });

        for(int i = 0;i<T;i++) {
            bw.write(matrix[i][0]+" "+matrix[i][1]+"\n");
        }

        bw.close();
    }

---

레퍼런스 코드

참고 링크 : https://st-lab.tistory.com/113