문제
N개의 단어가 주어졌을 때, 다음 규칙에 따라 정렬하여 중복 없이 출력하는 문제다. 정렬 기준은 1) 길이가 짧은 순, 2) 길이가 같으면 사전 순이다.
입력
- 첫째 줄: 단어 수 N (1 이상 20,000 이하)
- 둘째 줄부터 N개 줄: 알파벳 소문자로 이루어진 단어 (길이 50 이하)
출력
정렬 조건에 맞게 단어를 중복 제거하여 한 줄에 하나씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
13 but i wont hesitate no more no more it cannot wait im yours | i im it no but more wait wont yours cannot hesitate |
풀이
커스텀 비교자를 적용한 정렬로 길이 우선, 사전순 차순의 다중 기준 정렬을 수행하고, 정렬 후 인접 중복을 검사하여 중복을 제거한다.
- N개의 단어를
String[]배열에 저장한다. - 익명
Comparator를 사용해 길이가 다르면 길이 오름차순, 같으면compareTo로 사전 순 정렬한다. - 정렬 후 첫 번째 단어를 출력하고, 이후 단어가 바로 앞 단어와 다를 때만 출력하여 중복을 제거한다.
핵심 아이디어: 정렬 후 인접 비교로 중복을 제거하는 방식은 HashSet보다 간단하고, 이미 정렬이 완료된 상태이므로 동일 단어는 반드시 인접해 있음이 보장된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
public class Day03BOJ1181단어정렬 {// 1181
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
String[] arr = new String[num];
for (int i = 0; i < num; i++) {
arr[i] = br.readLine();
}
Arrays.sort(arr, new Comparator<String>() {
@Override // 이부분은 구글...
public int compare(String s1, String s2) {
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
} else {
return s1.length() - s2.length();
}
}
});
System.out.println(arr[0]);
for (int i = 1; i < num; i++) {
if (!arr[i].equals(arr[i - 1])) {
System.out.println(arr[i]);
}
}
}
}복잡도
- 시간: O(N log N) — 비교 정렬, 문자열 비교 시 단어 길이 L을 곱하면 O(N L log N)
- 공간: O(N) — 단어 배열 저장