[백준] 1181 단어 정렬 | 문자열, 정렬 | 실버 Ⅴ | JAVA 💡Arrays.sort

📌 문제

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

 

✔️ 정답 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));        
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        String[] s = new String[n];
        
        for (int i = 0; i<n; i++) {
            s[i] = br.readLine();
        }
        
        Arrays.sort(s, new Comparator<String>() {
            @Override
            public int compare(String a, String b){
                if (a.length() == b.length()) {
                    return a.compareTo(b);
                }
                return a.length() - b.length();
            }
        });
        
        sb.append(s[0]+'\n');
        
        for (int i = 1; i<n; i++){
            if (!s[i].equals(s[i-1])) 
                sb.append(s[i]+'\n');
        }
        
        bw.append(sb);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

⭐ Arrays.sort

✅ Comparator

Comparator는 두 객체를 비교하여 정렬 순서를 정의하는 인터페이스입니다.

compare 메서드를 통해 두 객체를 비교하고, 그 결과를 정수로 반환합니다. 

이때, 음수면 첫 번째 객체가 두 번째 객체보다 "앞"에 있어야 한다는 뜻입니다. 따라서 정렬 시 첫 번째 객체가 우선적으로 위치합니다.

양수면, 첫 번째 객체가 두 번째 객체보다 "뒤"에 있어야 한다는 뜻입니다. 그러므로 정렬 시 첫 번째 객체가 뒤로 밀려납니다.

0이면, 두 객체가 동일하다는 뜻으로, 이 경우에는 위치가 바뀌지 않습니다.

✅ 비교 로직

1️⃣ 길이 비교 

return a.length() - b.length();

예를 들어, a의 길이가 3이고 b의 길이가 5일 경우:

3 - 5는 음수(−2)를 반환합니다. 이는 a가 b보다 짧으므로, a가 정렬 결과에서 b보다 앞에 위치해야 함을 의미합니다.

만약 a의 길이가 5이고 b의 길이가 3일 경우:

5 - 3는 양수(2)를 반환합니다. 따라서 a가 b보다 뒤에 위치해야 함을 나타냅니다.

• 음수: 첫 번째 문자열 a의 길이가 두 번째 문자열 b의 길이보다 짧음을 의미합니다. 따라서 a가 b보다 앞에 위치해야 합니다.
• 양수: 첫 번째 문자열 a의 길이가 두 번째 문자열 b의 길이보다 길음을 의미합니다. 따라서 a가 b보다 뒤에 위치해야 합니다.
• 0: 두 문자열의 길이가 같음을 의미하며, 이 경우에는 사전 순으로 비교해야 합니다.

2️⃣ 사전 순 비교

if (a.length() == b.length()) {
	return a.compareTo(b);
}

 

예를 들어, a가 "apple"이고 b가 "banana"일 경우:

a.compareTo(b)는 음수를 반환합니다. 이는 "apple"이 "banana"보다 사전 순으로 앞에 있음을 의미합니다.

만약 a가 "banana"이고 b가 "apple"일 경우:

a.compareTo(b)는 양수를 반환합니다. 이는 "banana"가 "apple"보다 사전 순으로 뒤에 있음을 나타냅니다.

• 음수: 문자열 a가 문자열 b보다 사전 순으로 앞에 있음을 의미합니다.
• 양수: 문자열 a가 문자열 b보다 사전 순으로 뒤에 있음을 의미합니다.
• 0: 두 문자열이 동일함을 의미합니다.

 

✅ 정렬되는 과정

위에 설명한 것과 같이 만약 첫 번째 요소가 두 번째 요소보다 짧은 경우, 즉 음수를 반환하면, 첫 번째 요소는 배열의 앞부분에 위치하게 됩니다. 반대로, 양수를 반환하면 첫 번째 요소는 뒤로 밀려나고, 이 과정을 통해 두 요소의 위치가 바뀌게 됩니다.

이러한 방식으로 반환된 값이 음수인지, 양수인지에 따라 위치를 변경하는 과정을 반복하면서 알고리즘이 반복되는 동안 더 이상 요소의 위치가 변경되지 않으면, 즉 모든 요소가 이미 정렬된 상태라면 알고리즘은 종료됩니다. 

 

⭐ 중복 제거

✅ for문 이용

sb.append(s[0]+'\n');
        
for (int i = 1; i<n; i++){
	if (!s[i].equals(s[i-1])) 
		sb.append(s[i]+'\n');
}

 

첫 번째 문자열을 추가한 후, 두 번째 문자열부터 이전 문자열과 비교합니다.

동일한 문자열은 건너뛰고, 다른 문자열만 추가하여 중복을 피합니다.

 

set으로 중복 없애고 list 변경 후, Collections.sort로 람다식으로 정렬할 때 최악의 시간복잡도, 배열로 Arrays.sort에서 람다식이 아닌 compare메서드 오버라이드해서 메모리, 시간 둘 다 최소

 

처음 보거나 아는데도 활용을 못할 때마다 좀 괴롭다ㅎ

하다보면 익숙해지겠지..
원래 알던 것만 잘하고, 모르는 걸 더 습득하지 못하는 거 같다.
화이팅하자