문제 설명
알파벳 소문자로 이루어진 단어 N개가 주어진다.
이 단어들을 다음 기준에 따라 정렬해야 한다.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
- 중복된 단어는 하나만 남긴다
입력
첫째 줄에 단어의 개수 N이 주어진다.
1 ≤ N ≤ 20000다음 줄부터 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문제 해결 아이디어
이 문제의 핵심은 두 가지이다.
1. 중복 제거
2. 커스텀 정렬일반적인 오름차순 정렬이 아니라
- 문자열 길이 우선
- 길이가 같으면 사전순
으로 정렬해야 한다.
즉, 정렬 기준을 직접 정의하는 Comparator가 필요하다.
내가 작성한 코드
나는 List<String>에 단어를 넣을 때
이미 존재하는 단어인지 확인해서 중복을 제거한 뒤 정렬했다.
코드
import java.util.*;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<String> s = new ArrayList<>();
for(int i = 0; i < N; i++) {
String input = sc.next();
if(!s.contains(input))
s.add(input);
}
s.sort(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if(s1.length() == s2.length())
return s1.compareTo(s2);
return s1.length() - s2.length();
}
});
for(String res : s)
System.out.println(res);
}
}강의 코드
강의에서는 먼저 배열에 모든 단어를 저장한 뒤 정렬하고,
정렬된 상태에서 이전 단어와 비교하여 중복을 제거했다.
코드
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] words = new String[N];
for (int i = 0; i < N; i++)
words[i] = sc.next();
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length())
return o1.compareTo(o2);
return o1.length() - o2.length();
}
});
System.out.println(words[0]);
for (int i = 1; i < N; i++)
if (!words[i].equals(words[i - 1]))
System.out.println(words[i]);
}
}내 코드 vs 강의 코드 비교
1. 중복 제거 시점 차이
내 코드
if(!s.contains(input))
s.add(input);입력받을 때 바로 중복 제거
강의 코드
정렬 후
이전 단어와 현재 단어 비교출력 단계에서 중복 제거
핵심 차이
| 방식 | 특징 |
|---|---|
| 내 코드 | 입력 단계에서 중복 제거 |
| 강의 코드 | 정렬 후 중복 제거 |
2. 성능 차이
내 코드
List.contains()는 내부적으로 선형 탐색이기 때문에
한 번 contains = O(N)입력마다 이것을 수행하면 전체적으로
O(N²)까지 커질 수 있다.
강의 코드
- 배열 저장: O(N)
- 정렬: O(N log N)
- 중복 제거 출력: O(N)
즉 전체적으로
O(N log N)으로 더 효율적이다.
3. 정렬 방식은 동일
두 코드 모두 같은 Comparator를 사용한다.
if (문자열 길이 같음)
사전순 비교
else
길이 비교즉 정렬 기준은 완전히 같다.
커스텀 정렬 정리
이 문제의 핵심 개념 중 하나가 바로 커스텀 정렬이다.
기본 정렬은 숫자나 문자열의 기본 오름차순 정렬만 해준다.
하지만 이 문제처럼
길이 우선
같으면 사전순같은 조건이 있으면 직접 비교 기준을 만들어야 한다.
Comparator란?
정렬 기준을 직접 정의하는 인터페이스이다.
형태는 다음과 같다.
new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
...
}
}compare의 반환값 의미
음수 → o1이 앞
0 → 동일
양수 → o2가 앞이 문제의 Comparator
if (o1.length() == o2.length())
return o1.compareTo(o2);
return o1.length() - o2.length();의미는 다음과 같다.
-
길이가 같으면
→compareTo()로 사전순 비교 -
길이가 다르면
→ 길이가 짧은 것이 먼저 오도록 정렬
compareTo()란?
문자열의 사전순 비교 메서드이다.
예
"abc".compareTo("abd")결과는 음수이다.
즉
abc 가 abd 보다 앞선다핵심 개념
1. 문자열 길이 비교
s1.length() - s2.length()길이가 짧은 문자열이 먼저 오도록 정렬
2. 사전순 비교
s1.compareTo(s2)3. 정렬 후 중복 제거
정렬이 끝나면 같은 문자열은 서로 붙어 있게 된다.
그래서
현재 값 != 이전 값만 확인하면 중복 제거가 가능하다.
시간 복잡도
내 코드
- 입력하면서
contains()검사 - 최악의 경우
O(N²)강의 코드
- 배열 저장: O(N)
- 정렬: O(N log N)
- 출력: O(N)
전체
O(N log N)정리
이 문제는 단순 문자열 정렬 문제가 아니라
중복 제거 + 커스텀 정렬이 함께 들어간 문제였다.
내 코드는 입력 단계에서 중복을 제거했고,
강의 코드는 정렬 후 중복을 제거했다.
풀이 방식의 핵심 차이는 다음과 같다.
내 코드 → contains로 중복 제거
강의 코드 → 정렬 후 인접 비교로 중복 제거성능 면에서는 강의 코드가 더 좋다.
특히 contains()는 선형 탐색이기 때문에 입력 크기가 커질수록 불리하다.
또한 이 문제를 통해 다음과 같은 커스텀 정렬 패턴을 익힐 수 있다.
- 길이 기준 정렬
- 길이가 같으면 사전순 정렬
- Comparator 직접 구현
즉, 이 문제는
문자열 정렬 문제에서 Comparator를 어떻게 사용하는지 익히기 좋은 대표 문제라고 볼 수 있다.
