SWEA[7701] - 염라대왕의 이름 정렬[D4]

링크

SWEA[7701]

문제설명

• 정렬
• 중복제거

문제풀이

• 효율적인 자료구조
• 효율적인 알고리즘

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

public class Solution7701_TreeSet {

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/7701.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());

        for (int test_case = 1; test_case <= T; test_case++) {
            // 입력
            int N = Integer.parseInt(br.readLine());
            TreeSet<String> s = new TreeSet<String>(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    // TODO Auto-generated method stub
                    if(o1.length() != o2.length()) {
                        return o1.length() - o2.length();
                    }
                    else {
                        int max=o1.length();
                        int idx=0;
                        while(idx<max) {
                            if(o1.charAt(idx) != o2.charAt(idx)) {
                                return o1.charAt(idx) - o2.charAt(idx);
                            }
                            idx++;
                        }
                        return 0;
                    }
                }
            });

            String input;
            for (int i = 0; i < N; i++) {
                input = br.readLine().trim();
                if(!s.contains(input)) {
                    s.add(input);
                }
            }


            System.out.println("#"+test_case);
            StringBuilder sb = new StringBuilder();
            int qsize = s.size();
            for (int i = 0; i < qsize; i++) {
                sb.append(s.pollFirst()).append("\n");
            }
            System.out.print(sb);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• O(N) = contains 고려하면서 input 넣을 때 + 정렬(NlogN) = N^2 + NlogN = N^2 = 20000^2 = 4*10^8
  • 테케 50개라 터질만함
• String의 compareTo는 길이까지 비교해주지는 못한다.
  • System.out.println("asdf".compareTo("f"));
  • 음수가 나옴 a와 f만을 비교하기 때문
• PQ같은경우 길이별로 PQ만들어서 하면 좀 더 빠르게 하더라

잘한점

• 그냥 PriorityQueue, TreeSet공부함

시간

자료구조	알고리즘	시간
Array	Contains로 체크	시간초과
	출력하면서 중복제거	0.85s
PriorityQueue	Contains로 체크	시간초과
	출력하면서 중복제거	0.6s
TreeSet	알아서 중복제거	0.6s