[백준](2024)단어 정렬(설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/1181

 

 

난이도		알고리즘
	실버5	문자열, 정렬

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 2초 / 256MB

 

알파벳 소문자로 이루어진 단어 N개, 길이가 같으면 사전 순으로, 길이가 다르면 길이순으로 정렬

*중복 단어 distinct

* (1 ≤ N ≤ 20,000) 

* 단어 :  문자열의 길이는 50을 넘지 않는다.

 

 

 

 

2. 설계/검증 

입력

-N

-words

 

설계 

정렬 

- Comparator이용

 

출력

 - 정렬 후 이전 값과 같으면 출력 안 함. (중복된 값) 

 

시간 복잡도	최악의 경우	공간 복잡도
O(N * M * log N)	3,000,000	O(N * M)

 

 

 

 

3. 정상 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // Scanner 객체 생성
        Scanner scan = new Scanner(System.in);
        // 단어의 개수 입력
        int N = scan.nextInt();
        List<String> words = new ArrayList<>();
        // 단어 입력
        for (int i = 0; i < N; i++) {
            String word = scan.nextLine();
            words.add(word);
        }

        // 길이가 짧은 것부터, 길이가 같으면 사전순으로 정렬
        Collections.sort(words, new Comparator<String>() {

            @Override
            public int compare(String s1, String s2) {
                // 길이가 잛은 순서대로
                if (s1.length() != s2.length()) {
                    return s1.length() - s2.length();
                }
                // 길이가 같으면 사전 순으로 정렬
                return s1.compareTo(s2);
            }
        });

        // 중복을 제거하기 위해 Set 사용
        Set<String> uniqueWords = new LinkedHashSet<>(words);

        // 정렬된 결과 출력
        for (String uniWd : uniqueWords) {
            System.out.println(uniWd);
        }
    }
}

 

 

 

 

추가 정리

set

중복 허용하지 않는 컬렉션

HashSet

 중복 단어 입력시 하나만 남겨둔다.

LinkedHashSet

중복을 허용하지 않으며, 요소의 순서를 유지하는 특징이 있다.