염라대왕 이름 정렬

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG&categoryId=AWqU0zh6rssDFARG&categoryType=CODE

SW Expert Academy

Treeset, list 등을 이용하여 푸는 방식은 많지만 우선 순위 큐가 가장 적합하다 생각했다.

 

알고리즘

1. 입력을 받으면서 우선 순위 큐에 넣는다. 이름은 객체로 받았다.

-> ComparTo 함수를 만들어도 된다.

 

2. 객체 비교를 하는데 먼저 길이를 비교하였고, 길이가 같으면

반복문을 통해 사전 순으로 앞선 것을 오름차순 정렬했다.

 

3. 중복된 문자를 제거하기 위해 변수 하나 이용해서 오름차순 정렬된 값과 비교하여 출력한다.

 

주의사항

1. 앞 글자만 비교해서는 안된다. 실제 사전처럼 앞글자가 같으면 다음글자, 다다음글자 순서대로 비교한다.

2. 중복제거에도 다양한 방법이 있다. String 함수를 이용해서 정렬해도 된다.

 

구현

class pr implements Comparable<pr>{
    String name;

    public pr(String name) {
        super();
        this.name = name;
    }

    @Override
    public int compareTo(pr o) {
        if(this.name.length() - o.name.length() == 0) // 같으면
        {
            for (int i = 0; i < o.name.length(); i++) {  //앞 글자가 같으면 다음 글자를 비교한다.
                if(this.name.charAt(i) - o.name.charAt(i) >0) 
                    return 1;
                else if(this.name.charAt(i) - o.name.charAt(i) <0)
                    return -1;
            }
        }
        return this.name.length() - o.name.length();
    }

}
class Solution_염라대왕이름정렬
{
    static int N;

    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            StringTokenizer s ;
            PriorityQueue<pr> pqueue = new PriorityQueue<pr>();
//            ArrayList<String> list = new ArrayList<String>();

            N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine().trim());
                //String a = ;
//                list.add(a);
                pqueue.offer(new pr(s.nextToken()));
            }

///////////////////list로 해서 정렬해도 된다.//////////////////////////

//            Collections.sort(list, new Comparator<String>() {
//
//                @Override
//                public int compare(String o1, String o2) {
//                    if(o1.length() == o2.length())
//                        return o1.charAt(0) - o2.charAt(0);
//                    return o1.length()-o2.length();
//                }
//            });

            System.out.println("#"+test_case);
            pr p;
            String cnt="";
            while(!pqueue.isEmpty())
            {
                p = pqueue.poll();
                // 정렬 되 있기 때문에 cnt를 활용하여 cnt가 바뀌면 출력한다.
                if(!p.name.equals(cnt)) { 
                    System.out.println(p.name);
                    cnt = p.name;
                }
            }
        }
    }
}