[BOJ][JAVA] 10814: 나이순 정렬

 

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

10814번: 나이순 정렬

---

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

class Main{
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] arr = new String[n];
        sc.nextLine();
        for(int i=0; i<n; i++){
            arr[i] = sc.nextLine();
        }
        int[] ageSize = new int[n];

        StringBuilder sb = new StringBuilder();
        int idx = 0;
        for(String input : arr){
            String[] sp = input.split(" "); // 앞 원소가 나이
            ageSize[idx++] = Integer.parseInt(sp[0]);
        }
        Arrays.sort(ageSize);
        int cnt = 0;
        while(cnt < n){
            for(String input : arr){
                String[] sp = input.split(" "); // 앞 원소가 나이
                if(ageSize[cnt] == Integer.parseInt(sp[0])){
                    if(sb.indexOf(input) == -1){
                        sb.append(input).append("\n");
                        break;
                    }
                }
            }
            cnt++;
        }

        System.out.println(sb);
        sc.close();
    }
}

오답노트(푸는 동안 사고과정 및 개선점)

단순하게 생각해서 풀었는데 시간초과가 나버렸다. 처음부터 로직을 다시 짜야되나..

---

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

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<String[]> 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 String[]{Integer.toString(age), name});
        }

        members.sort((m1, m2) -> {
            if (m1.age == m2.age) {
                return 0;
            }
            return m1.age < m2.age ? -1 : 1;
        });

        for (String[] member : members) {
            System.out.println(member[0] + " " + member[1]);
        }
    }
}

 

여기서 나머지는 어차피 똑같은 구조니까 정렬 부분만 보도록 하자. 람다식을 사용해봤다.

members.sort((m1, m2) -> {
    if (m1.age == m2.age) {
        return 0;
    }
    return m1.age < m2.age ? -1 : 1;
});

Collections에 있는 sort는 Comparator을 사용하는데, 람다식으로 줄여서 쓰는 경우다. m1, m2는 비교할 두 객체이다. 여기서는 List를 갖는 member가 된다.

Comparator의 sort를 override해서 사용하는데, 0, -1, 1의 반환 값 차이만 이해하면 끝이다. 이 코드에서 0은 정렬 방향 그대로, -1이면 m1이 m2보다 작은걸로 배치, 1이면 m1이 m2보다 큰거로 배치한다.

 

0일 때 순서가 바뀔 수도 있지않느냐 할 수 있는데, 이때 Collections.sort는 입력된 순서를 유지하면서 정렬해준다. stable 정렬 알고리즘 을 사용하기 때문이다.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^