1181 : 단어 정렬

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

1181번: 단어 정렬

이번 문제는 단어 정렬이다.

이 문제는 우선순위 큐를 이용해서 풀었는데, 우선순위 큐의 정렬방식이 Heap 정렬이기 때문에 좋은 효율을 보일 것이라고 판단, 사용하게 되었다.

 

다만 이 과정에서 문자열이 들어가기 때문에, Comparator를 직접 구현해줘야 했고, 해당 Comparator는 

Class MyCompartor 부분에 구현을 했다.

Comparable과 Compartor 두 개의 비교자에 대해서 차후 후술할 예정이다.

 

해당 Comparator를 사용하도록 초기화 후, 우선순위 큐에 문자열을 넣게 되면, 자동으로 문자열이 비교가 되어서 정렬된다.

 

알파벳을 오름차순으로 정렬하기 위해서 우선순위 큐를 사용할 방법을 생각해봤다.

(글을 쓰다보며 생각해보니 오름차순이라면 아주 우선순위 큐만 떠오르니 이거 나름대로 문제일 거 같기도 하다. 무지성 우선순위 큐는 곤란한데...)

이번 문제는 근데 우선순위 큐를 사용해서 그런지는 몰라도 코드를 정말 깔끔하게 짰다는 생각이 들어서 올리게 되었다.

(매우 주관적인 생각입니다..)

 

<코드 설명>

우선순위 큐에서 String을 순서대로 받을 때 순위를 정하기 위해서 문제에 나와 있는 두가지 조건인 단어의 길이와 사전순서를 MyComparator 클래스에 넣었다.

먼저 그 길이가 같을 경우 단순 길이비교 반환을 통해서 우선순위를 반환해주었고, 길이가 같을 경우 길이가 각 알파벳을 char형태로 반환해서 char 형태의 알파벳을 비교해 반환하였다.

이 경우 완전히 같은 문자일 경우는 배제되지 않는데, 이 경우 배제를 위해서

출력시 미리 출력한 문자와 우선순위 큐의 다음 출력순서의 문자열이 동일하면 출력하지 않도록 구성했다.

아래는 최종적으로 통과를 받은 코드 전문이다.

import java.util.*;
class MyComparator implements Comparator<String>{

	@Override
	public int compare(String o1, String o2) {
		// TODO Auto-generated method stub
		if(o1.length()==o2.length())
		{
			int answer=0;
			for(int i=0;i<o1.length();i++)
			{
				if(o1.charAt(i)!=o2.charAt(i)) {
					answer=o1.charAt(i)-o2.charAt(i);
					break;
				}
			}
			return answer;
		}
		else {
			return o1.length()-o2.length();
		}
	}

}
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		
		PriorityQueue<String> init=new PriorityQueue<String>(new MyComparator());
		for(int i=0;i<N;i++)
		{
			init.add(sc.next());
		}
		int size=init.size();
		for(int i=0;i<size;i++)
		{
			String answer=init.poll();
			if(!answer.equals(init.peek()))
				System.out.println(answer);
		}
	}
}