[CLASS 2: 문자열] 백준 1181 단어 정렬

1181번: 단어 정렬

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));
    StringBuilder sb = new StringBuilder();
    int n = Integer.parseInt(br.readLine());
    int max_length = 0;
    String[] arr = new String[n];
    for (int i = 0; i < n; i++) {
      arr[i] = br.readLine();
      if (max_length < arr[i].length()) {
        max_length = arr[i].length();
      }
    }
  
    for (int i = 1; i <= max_length; i++) { // max_length 까지만 반복
      ArrayList<String> mini_list = new ArrayList<>();
      for (int j = 0; j < n; j++) {
        if (arr[j].length() == i) {
          if (!mini_list.contains(arr[j])) {
            // mini_list 내에 해당 요소가 없으면 add (중복 방지)
            mini_list.add(arr[j]);
          }
        }
      }
      // 한 길이가 끝날 때마다 mini_list를 정렬하여 sb에 쌓음
      // ArrayList를 정렬하기 위해 Collections.sort() 사용
      Collections.sort(mini_list);
      for (String ele : mini_list) {
        sb.append(ele).append("\n");
      }
    }

    System.out.print(sb);
    br.close();
  }
}

• 1부터 max_length까지 반복하는 동안 주어진 배열에서 해당하는 길이의 문자열을 골라 mini_list에 넣고, 한 길이가 끝날 때마다 mini_list를 정렬하여 sb에 쌓는 코드이다.
• ArrayList를 정렬하기 위해서는 Arrays.sort()를 사용하는 배열과 달리 Collections.sort()가 필요하다.

 

하지만 위의 코드는 832ms 라는 꽤나 긴 시간이 걸리는 단점이 있다.

832ms ... ㄷㄷ

 

 

그리고 그 이유는 다음과 같다.

 

1. ArrayList.contains() 사용의 비효율성

mini_list.contains(arr[j])는 mini_list 내에서 중복을 체크하는 부분이다. 이 연산은 O(n) 시간 복잡도를 가지며, mini_list의 크기가 클수록 시간이 많이 소요된다. 특히 for 루프 내에서 매번 contains()를 호출하므로, 시간이 많이 걸리게 된다.

 

2. Collections.sort() 호출 빈도

Collections.sort(mini_list)는 반복문마다 ArrayList를 정렬한다. 이는 O(n log n)의 시간 복잡도를 가지며, 이 작업을 여러 번 수행하면 시간 소요가 커진다.

 

3. 중복 제거 후 정렬

중복을 제거하는 과정과 정렬 과정이 따로 이루어지기 때문에 불필요한 시간이 소비된다. 효율적으로 정렬된 상태에서 중복을 제거하면 이중으로 작업하지 않아도 된다.

 

 

 

 

HashSet 이란?

HashSet은 Java의 컬렉션 프레임워크 중 하나로, 중복을 허용하지 않는 데이터 집합을 저장하는 자료구조이다. 내부적으로 해시 테이블을 사용하여 데이터를 저장하며, 이를 통해 빠른 탐색, 추가, 삭제 작업을 할 수 있다. HashSet은 특히 중복된 값을 자동으로 제거해야 할 때 유용하다.

주요 특징:

1. 중복을 허용하지 않음: 같은 값이 두 번 저장되지 않는다.
2. 순서가 없음: 저장된 요소들의 순서는 보장되지 않는다. (정렬이 필요하면 TreeSet 또는 List와 같은 다른 자료구조를 사용해야 한다.)
3. 빠른 탐색 및 수정: 일반적으로 삽입, 삭제, 검색 작업이 O(1)의 시간 복잡도를 가진다. (내부적으로 해시 테이블을 사용하기 때문에 매우 빠름)

 

 

 

아래는 시간복잡도를 개선하기 위해 새로 작성한 코드이다.

중복 제거를 위해 입력을 HashSet으로 받고, ArrayList로 변환하여 Collections.sort() 메소드로 리스트를 정렬했다.

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));
    StringBuilder sb = new StringBuilder();
    int n = Integer.parseInt(br.readLine());

    // HashSet을 사용함으로써 자동으로 중복을 제거하면서 입력받음
    Set<String> uniqueStrings = new HashSet<>();
    for (int i = 0; i < n; i++) {
      uniqueStrings.add(br.readLine());
    }

    // Set을 List로 변환하여 정렬
    List<String> sortedList = new ArrayList<>(uniqueStrings);
    Collections.sort(sortedList, (a, b) -> {
      if (a.length() != b.length()) {
        return Integer.compare(a.length(), b.length());
      } else {
        return a.compareTo(b);  // 길이가 같으면 사전순 정렬
      }
    });

    for (String str : sortedList) {
      sb.append(str).append("\n");
    }

    System.out.print(sb);
    br.close();
  }
}

• Collections.sort(정렬할 리스트, 정렬 기준) 메소드 내에서 정렬 기준으로는 람다식을 사용했다.

 

람다식만 따로 떼서 보면 이렇다.

(a, b) -> {
    if (a.length() != b.length()) {
        return Integer.compare(a.length(), b.length());
    } else {
        return a.compareTo(b);  // 길이가 같으면 사전순 정렬
    }
}

이 람다식은 두 문자열 a와 b의 정렬 순서를 결정하는 정렬 기준을 정의한다.

1. if (a.length() != b.length()):
   • 우선, 두 문자열의 길이를 비교한다.
   • 길이가 다르면: a.length()와 b.length()를 비교하여, 더 짧은 문자열이 먼저 오도록 정렬한다.
2. return Integer.compare(a.length(), b.length());:
   • Integer.compare()는 두 정수를 비교하는 함수로, 첫 번째 인자와 두 번째 인자를 비교한다.
   • 만약 a.length()가 b.length()보다 짧으면 음수(-1), 같으면 0, 길면 양수(1)를 반환한다. 이 값에 따라 Collections.sort()가 문자열의 순서를 결정한다.
3. else { return a.compareTo(b); }:
   • 만약 두 문자열의 길이가 같다면, compareTo() 메서드를 사용하여 사전순 정렬을 수행한다.
   • a.compareTo(b)는 String 클래스의 내장 메서드로, a와 b를 사전순(알파벳순)으로 비교하여 정렬 순서를 결정한다. a가 b보다 먼저 오면 음수(-1), 같으면 0, 나중에 오면 양수(1)를 반환한다.

요약:

• 1차 기준: 문자열의 길이에 따라 정렬합니다. 더 짧은 문자열이 먼저 온다.
• 2차 기준: 만약 길이가 같다면, 문자열을 사전순으로 정렬한다.

이 방식으로 List가 문자열 길이에 따라 정렬되며, 길이가 같을 경우 사전순으로 정렬된다.

채점해보면 시간복잡도가 눈에 띄게 줄어든 것을 확인할 수 있다.

 

👏🏻👏🏻👏🏻