1181번(단어정렬)

첫 시도

• 조건
  1. 단어의 길이
  2. 단어의 사전 순
• 시간제한은 2초, N = 2 * 10^4이므로 N^2으로 해결하기에는 시간이 아슬아슬
• Collections.sort로 조건을 설정해 정렬 → O(N+nlogn)
• HashSet을 사용해 중복을 제거하려 했지만 클래스를 원소로 사용하게 되면 인스턴스 변수의 중복확인이 불가능하므로 중복되어 저장됨

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;

        int N = Integer.parseInt(br.readLine());
        HashSet<Word> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            set.add(new Word(input,input.length()));
        }

        List<Word> list = new LinkedList(set); // set은 Collections.sort 사용 불가능, list로 변환
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            Word a = list.get(i);
            System.out.println(a.value);
        }


    }

}
class Word implements Comparable<Word>{
    String value;
    int length;

    Word(String value, int length) {
        this.value = value;
        this.length = length;
    }

    @Override
    public int compareTo(Word o) {
        if(this.length == o.length){
           return this.value.compareTo(o.value);
        }
        else if(this.length > o.length){
            return 1;
        }
        else {
            return -1;
        }
    }
}

해결

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;

        int N = Integer.parseInt(br.readLine());
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            set.add(input);
        }

        List<String> list = new LinkedList(set); // set은 Collections.sort 사용 불가능, list로 변환
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length() == o2.length()){
                    return o1.compareTo(o2);
                }
                else {
                    return o1.length() - o2.length();
                }
            }
        });

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }


    }

}

참고

• 직접구현