[JAVA] BOJ(백준) - 단어 정렬 - 1181

문제내용

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

1181번: 단어 정렬

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다

---

문제풀이

기본적인 정렬문제로 Comparator만 쓸줄 안다면 풀수 있는 문제라고 생각한다.

Comparator는 한마디로 특별한(?) 정렬이 필요할때 사용자 입맛에 맞게끔 정렬해주는 자바의 인터페이스라는걸 알아두고 가자.

문제는 다음과 같은 과정을 거쳐서 푼다.

 

1. 중복되는 단어는 하나만 출력한다.
   이말은 곧 중복을 제거해야된다는 뜻이다. 자바에서 중복을 손쉽게 제거하기 위해 HashMap , HashSet , TreeSet 등을 이용할 수 있다. 여기서 필자는 HashSet을 이용했다.
2. 리스트에 중복제거한 단어 담아주기.
   리스트를 하나 추가해서 중복제거된 단어들을 담아준다.
3. 정렬하고 출력하기.
   2번에서 만든 리스트를 Compartor와 compareTo를 활용해 정렬하고, 출력해준다.
   
   참고로 위의 메소드를 사용할때
   반환값이 양수 = 위치 바꿈.
   반환값이 음수 or 0 = 위치 안바꿈.
   이라는걸 머리에 밖아두자~

그리고 Comparator를 쓸때 반환값에 return o1-o2; 이런식으로 반환값을 주는 사람들이 있는데, 이부분은 잘못된건 아니지만 만약 수가 o1,o2 자료형이 int형일때 수가 정수형 범위를 넘어가게 된다면 o1-o2를 할시에 오버플로 or 언더플로가 발생하게 된다.

따라서 수의 범위가 매우 클때 정확하게 비교하려면 부등호를 활용한 대소비교를 해줘야한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<String> list = new ArrayList<>();
		HashSet<String> set = new HashSet<String>();
		for(int i=0; i<n; i++) //중복단어 제거
			set.add(br.readLine());
		
		
		Iterator<String> iter = set.iterator();
		while(iter.hasNext()) //리스트에 담아주기
			list.add(iter.next());
		
		
		//정렬 -> 단어길이 우선, 같으면 사전순.
		Collections.sort(list, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				int s1 = o1.length();
				int s2 = o2.length();
				if(s1>s2) return 1;
				else if(s1<s2) return -1;
				
				else {//단어길이가 같으면 사전순으로.
					int headValue = o1.compareTo(o2);
					return headValue;
				}
			}
		});
		
		for(String s:list) 
			System.out.println(s);
	}
}

---

마치며

앞서 말했다시피 Comparator를 알고 있다면 쉽게 풀수 있는 문제다. Compartor를 익히자.