10814번(나이순 정렬)

첫 시도

• 조건
  1. 나이가 어린 순
  2. 먼저 가입한 순
• Person 클래스를 생성하고 이를 원소로 하는 LinkedList 생성
• Person에 Comparable을 implements해 compareTo 구현, Collections.sort로 정렬
• N = 100000, 시간 제한 3초 → 2N + nlogn로 충분할 것으로 예상 → 왜 시간초과?

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        List<Person> list = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int age = Integer.parseInt(input[0]);
            String name = input[1];
            list.add(new Person(age,name,i));
        }

        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            Person temp = list.get(i);
            sb.append(temp.age).append(" ").append(temp.name).append("\n");
        }
        System.out.println(sb.toString());
    }

}
class Person implements Comparable<Person>{
    int age;
    String name;
    int id;

    public Person(int age, String name, int id) {
        this.age = age;
        this.name = name;
        this.id = id;
    }

    @Override
    public int compareTo(Person o) {
        if(this.age == o.age){
            return this.id - o.id;
        }
        else {
            return this.age - o.age;
        }
    }
}

해결

• LinkedList로 list를 구현한게 문제
• LinkedList의 get메소드 시간복잡도는 O(n) → 값 출력 시 N^2
• 2N + nlogn (예상) → N + nlongn + N^2 (실제)
• ArrayList로 변경 → get메소드 시간복잡도 O(1) → 값 출력 시간복잡도 N

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Person> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int age = Integer.parseInt(input[0]);
            String name = input[1];
            list.add(new Person(age,name,i));
        }

        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            Person temp = list.get(i);
            sb.append(temp.age).append(" ").append(temp.name).append("\n");
        }
        System.out.println(sb.toString());
    }

}
class Person implements Comparable<Person>{
    int age;
    String name;
    int id;

    public Person(int age, String name, int id) {
        this.age = age;
        this.name = name;
        this.id = id;
    }

    @Override
    public int compareTo(Person o) {
        if(this.age == o.age){
            return this.id - o.id;
        }
        else {
            return this.age - o.age;
        }
    }
}

참고

• 직접구현