https://www.acmicpc.net/problem/1181
제출코드
import java.io.*;
import java.util.*;
class 단어정렬 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int repetition = Integer.parseInt(br.readLine());
String[] array = new String[repetition];
for (int i = 0; i < repetition; i++) {
String input = br.readLine();
array[i] = input;
}
String[] uniqueArr = sort(array);
for (String str : uniqueArr) {
System.out.println(str);
}
}
static String[] sort(String[] array) {
// 길이가 짧은 것 부터, 길이가 같으면 사전 순으로 정렬
Arrays.sort(array, (s1, s2) -> {
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
} else {
return Integer.compare(s1.length(), s2.length());
}
});
// 중복 제거
LinkedHashSet<String> set = new LinkedHashSet<>(Arrays.asList(array));
String[] uniqueArr = set.toArray(new String[0]);
return uniqueArr;
}
}모범답안
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
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());
String[] arr = new String[N];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine();
}
Arrays.sort(arr, new Comparator<String>() {
public int compare(String s1, String s2) {
// 단어 길이가 같을 경우
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
}
// 그 외의 경우
else {
return s1.length() - s2.length();
}
}
});
StringBuilder sb = new StringBuilder();
sb.append(arr[0]).append('\n');
for (int i = 1; i < N; i++) {
// 중복되지 않는 단어만 출력
if (!arr[i].equals(arr[i - 1])) {
sb.append(arr[i]).append('\n');
}
}
System.out.println(sb);
}
}알고리즘
- 먼저 문자열이 들어있는 배열을 만든다.
- 첫번째 정렬 조건인 '길이가 짧은 것부터'는 s1.length - s2.length로 구현할 수 있다.
- 만약 길이가 동일하면 두번째 정렬 조건인 '사전 순으로' 정렬한다. String의 경우 정렬의 조건을 명시하지 않아도 compareTo() 나 compare()를 실행하면 알아서 사전 순-> 만약 알파벳이 동일하면
으로 정렬해주기 때문에 s1.compareTo(s2)로 구현할 수 있다.
궁금한점
퀵소트가 가장 빠르기 때문에 항상 퀵소트를 사용해야 하는가??
비교
- Set, HashSet, LinkedHashSet
- Set은 인터페이스로써, 중복을 허용하지 않으며 순서를 보장하지 않는 자료형이다.
예를 들어 학번, 사원번호 등과 같은 로직에 활용할 수 있다. - Set의 구현체로 EnumSet, HashSet, LinkedHashSet, TreeSet 등이 있다.
-
Set을 구현하는 HashSet과 LinkedHashSet에 대해 알아보자.
HashSet의 작동방식은 HashMap과 거의 유사한데, 우선 HashMap을 복기해보자. -
HashMap은 자료형을 key와 value로 나눌 수 있으며, 중복과 순서를 보장하지 않는다.
이러한 로직을 HashSet에서 사용하는데, key에 저장할 값을 넣고 value에는 더미값(0,1 등 의미없는 값)을 넣는다. HashSet 역시 중복을 허용하지 않고, 순서를 보장하지 않는다. 저장할 때 ['Red', 'Blue', 'Orange', 'Black'] 순서로 넣더라도 실제 저장되는 순서는 다를 수 있다. -
물론 관련 메소드를 사용할 때 Map에서 사용하는 메소드가 아닌 Set에 대한 메소드를 사용한다.
-
LinkedHashSet은 HashSet과 모든 부분에서 동일하지만 순서를 유지한다는 특징이 있다. 하지만 이러한 특성 때문에 실행속도는 HashSet이 더 빠르다.
-
그렇다고 해서 인덱스가 있는 것은 아니다.
-
중복을 허용하지 않으며 순서를 보장하는 로직에선 LinkedHashSet을 사용하면 될 것이다.
LinkedHashSet<String> colors = new LinkedHashSet<>();
colors.add("red");
colors.add("blue");
colors.add("orange");
// 추가
colors.add("green");
// 삭제
colors.remove("blue");
// 수정
colors.add("yellow");
colors.remove("purple");
- 제출코드 실행시간: 580ms vs 380ms
- 시간복잡도
a) 입력 받기: N개의 문자열을 입력 받는 데 O(N)의 시간이 소요
b) 정렬: Arrays.sort() 메서드를 사용하여 문자열 배열을 정렬한다.
퀵소트 알고리즘을 사용하므로 평균적으로 O(N log N)의 시간 복잡도를 가진다.
하지만, 이 경우 Comparator를 사용하여 문자열의 길이와 사전 순으로 정렬 기준을 정의했다. 문자열 비교 연산의 시간 복잡도는 비교되는 문자열의 길이에 의존적이다.
최악의 경우, 모든 문자열이 길이가 같고 문자열 길이가 M이라고 할 때, 문자열 비교는 O(M)의 시간이 걸릴 수 있습니다.
따라서, 정렬의 총 시간 복잡도는 O(N log N * M)이 됩니다.
c) 중복 제거 및 출력: 마지막으로, 중복되지 않는 단어만 StringBuilder에 추가하고 출력하는 부분은 O(N)의 시간이 소요됩니다. 여기서 문자열 비교도 발생하지만, 정렬된 문자열에서 연속된 문자열만을 비교하므로, 이 부분의 시간 복잡도는 상대적으로 무시할 수 있습니다.
O(N log N * M)
정리
-
중복을 제거하기 위해 가장 효율적인 방법은 HashSet을 이용하는 것이다.
위 비교에서 if문 또는 for 문을 사용했던 것이 더 나은 방법인 줄 알았는데, 검색해본 결과 데이터가 많아질 경우 반복문을 사용하면 속도가 더 느려지기 때문에 HashSet을 이용하는 것이 좋다. -
수동으로 정렬 함수를 만드는 것보다, sort()와 Comparable, Comparator를 사용하는 것이 효율적이다 .
https://blog.naver.com/gujueng32/223385964041
참고한 링크
