[Java]백준1181-단어정렬

예전에 많이 듣던 노래당

문제 소개!

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

단어 정렬

실버5 

문제

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

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

단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 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

알고리즘 분류

• 문자열
• 정렬

 

---

문자열을 정렬해야하는 문제다. 자바에서는 compareTo를 이용해 문자열을 비교할 수 있다.

compareTo는 같은 위치에 있는 문자의 아스키 코드 차이값을 비교해서 리턴한다. (아스키 코드값 a: 97, A: 65)

 

우선 compareTo를 이용해 숫자를 비교한 경우

public class CompareToExample {
    public static void main(String[] args) {
        // 숫자를 문자열로 변환하여 비교
        String num1 = "123";
        String num2 = "456";

        // compareTo 결과 출력
        System.out.println(num1.compareTo(num2)); // 음수: num1 < num2
        System.out.println(num2.compareTo(num1)); // 양수: num2 > num1
        System.out.println(num1.compareTo("123")); // 0: num1 == "123"
    }
}

기준값이 비교하는 값보다 작으면 음수, 크면 양수, 같으면 0을 리턴

 

문자열을 비교한 경우도 마찬가지로

public class CompareStringsExample {
    public static void main(String[] args) {
        String str1 = "apple";
        String str2 = "banana";
        String str3 = "Apple"; // 대소문자 비교를 확인하기 위한 예시

        // compareTo 결과 출력
        System.out.println(str1.compareTo(str2)); // 음수: str1 < str2
        System.out.println(str2.compareTo(str1)); // 양수: str2 > str1
        System.out.println(str1.compareTo("apple")); // 0: str1 == "apple"
        System.out.println(str3.compareTo(str1)); // 음수: 대소문자 비교 (A < a)
    }
}

아스키 코드를 비교해 대문자가 소문자보다 작은 결과가 출력된다.

 

문제의 요구사항은 다음과 같다.

1. 문자열 길이순으로 정렬

2. 길이 같으면 사전순으로 정렬

3. 같은 글자 중복제거

 

사전 순 정렬은 길이가 같은 문자열의 각 단어를 비교해 다른 첫글자를 비교하면 되는데, 이를 compareTo를 사용하면 간단하게 비교할 수 있다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 1. 문자열 입력 받기
        int N = sc.nextInt();
        String[] str = new String[N];
        for (int i = 0; i < N; i++) {
            str[i] = sc.next();
        }
        // 2. 길이 비교
        for (int i = 0; i < N - 1; i++) {
            for (int j = 1; j < N - i; j++) {
                if (str[j].length() < str[j - 1].length()) {
                    // 짧은 단어를 앞으로
                    swap(str, j);
                } else if (str[j].length() == str[j - 1].length()) {
                     // 3. 길이가 같으면 문자열 비교
                    if (str[j].compareTo(str[j - 1]) < 0) {
                        swap(str, j);
                    }
                }
            }
        }
        // 4. 이전 단어와 다를 때만 출력
        System.out.println(str[0]);
        for (int i = 1; i < N; i++) {
            if (!str[i].equals(str[i - 1]))
                System.out.println(str[i]);
        }
    }

    public static void swap(String[] str, int j) {
        String tmp = str[j];
        str[j] = str[j - 1];
        str[j - 1] = tmp;
    }
}

위 코드에서 단어순 정렬은 그냥 알고있는 버블 정렬을 사용해보았다. (당연히 시간 효율이 좋지 않다.)

compareTo를 이용해 각 길이가 같을 때 문자를 비교했고, 중복 제거를 위해 이전과 겹치지 않는 단어만 출력하는 방식으로 풀이했다.

 

중복제거를 효율적으로 하기 위해선 set을, 정렬은 람다식을 이용하면 빠르다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 1. 문자열 입력 받기
        int N = sc.nextInt();
        String[] str = new String[N];
        for (int i = 0; i < N; i++) {
            str[i] = sc.next();
        }
        // 1. 중복 제거를 위해 Set 사용
        Set<String> set = new HashSet<>(Arrays.asList(str));
        str = set.toArray(new String[0]);

        // 2. 정렬
        Arrays.sort(str, (s1, s2) -> {
            if (s1.length() == s2.length()) {
                return s1.compareTo(s2); // 사전순 정렬
            }
            return s1.length() - s2.length(); // 길이순 정렬
        });

        // 3. 출력
        for (String s : str) {
            System.out.println(s);
        }
    }
}

- HashSet을 사용하여 중복 문자열 제거

 

• Arrays.asList(str)를 통해 문자열 배열 str을 리스트로 변환
• HashSet은 중복을 허용하지 않는 자료구조

• 배열로 변환:
  • set.toArray(new String[0])를 사용하여 중복이 제거된 문자열들을 다시 배열 형태로 환한다. (new String[0]으로 빈 배열을 생성해 타입만 지정할 수 있다.)

 

- Arrays.sort를 사용하여 정렬:

• 두 문자열 s1과 s2를 비교하여 정렬 기준을 지정한다.
• 길이 비교:
  • s1.length() - s2.length()를 사용하여 문자열 길이를 기준으로 오름차순 정렬
• 사전순 비교:
  • 길이가 같을 경우, s1.compareTo(s2)를 사용해 사전순으로 정렬합니다.
  • compareTo 메서드로 문자열의 각 문자를 아스키 코드로 변환하여 비교

중복이 제거되었으므로 Arrays.sort를 이용해 길이가 같을땐 사전순으로 정렬하고, else일땐 길이순으로 정렬하도록한다.

s1을 기준으로 비교하고 있으므로 결과가 음수가 나온다면 s1이 더 짧기 때문에 앞에 위치하게 된다.