백준 문제 풀이: [2571] [(수 정렬하기 2)] (JAVA)

---

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

문제 설명:

N개의 정수를 입력받아 이를 오름차순으로 정렬한 후 중복을 제거하고 출력하는 문제입니다. 단, 시간 복잡도를 줄이기 위해 빠른 정렬 알고리즘을 사용해야 합니다.

입력 크기가 최대 1,000,000이므로 정렬 및 출력의 효율성이 중요합니다.

---

문제 해결 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class s2751 {
    public static void main(String[] args) throws IOException {
        // 입력을 효율적으로 처리하기 위한 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 정수 배열 초기화
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // Arrays.sort를 사용하여 정렬 수행 (Dual-Pivot Quick Sort 알고리즘 사용)
        Arrays.sort(arr);

        // 출력 최적화를 위한 StringBuilder 사용
        StringBuilder sb = new StringBuilder();
        sb.append(arr[0]).append("\n"); // 첫 번째 값은 바로 추가

        // 중복 제거를 위한 비교 로직
        for (int i = 1; i < N; i++) {
            if (arr[i] != arr[i - 1]) { // 이전 값과 다를 때만 추가
                sb.append(arr[i]).append("\n");
            }
        }

        // 최종 출력
        System.out.print(sb);
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: Arrays.sort를 사용한 정렬. 이는 Java의 기본 정렬 알고리즘인 Dual-Pivot Quick Sort를 사용하며 평균 시간 복잡도는 O(N ⋅ log N)입니다.
• 구현 세부사항:
  • BufferedReader로 입력을 받아 I/O 성능을 최적화합니다.
  • StringBuilder를 사용하여 출력 과정을 효율적으로 처리합니다.
  • 중복 제거를 위해 정렬된 배열을 순회하면서 이전 값과 다른 경우만 출력에 추가합니다.
• 시간 복잡도 분석:
  • 정렬: O(N ⋅ log N), 여기서 N은 입력 크기입니다.
  • 중복 제거 및 출력: O(N).
  • 총 시간 복잡도: O(N ⋅ log N).

---

결과

예제 입력:

7
5
2
9
5
2
9
1

예제 출력:

1
2
5
9

 

---

추가로.. 첫번째, 두번째 제출했던 코드이다.

 

 

실패

제대로 정렬되고 중복 제거해 출력했는데 왜 틀렸는지 의문이었다. 

하지만, 다음과 같은 이유일 수도 있을 것이라고 한다. 

 

- 우선 set.stream().sorted(); 부분이 실제로 아무런 영향을 주지 않는다는 점이 문제이다.

- 그리고, set.stream().sorted();는 정렬된 스트림을 반환하지만, 이 결과를 저장하거나 활용하지 않으므로 set의 순서는 여전히 변경되지 않는다. HashSet은 순서를 보장하지 않는 자료구조이기 때문에 출력 결과의 순서가 정렬되지 않을 수 있다. 즉, 로컬에서 테스트한 데이터는 우연히 잘 출력되었을 수 있지만, 다른 입력에서는 정렬되지 않은 상태로 출력될 가능성이 있다.

 

- 찾아보니, HashSet은 정렬을 지원하지 않는다. 단지 넣은 키값과 HashSet의 테이블의 크기 (정확하게 말하면 크기 - 1)과 & 연산을 진행하여 테이블에 담기게 된다고 한다.

 

이 부분에 대해서는 좀 더 정확한 이유가 있다면 알려주시면 감사하겠습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class s2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < N; i++) {
            set.add(Integer.parseInt(br.readLine()));
        }

        set.stream().sorted(); // HashSet은 distinct() 사용하지 않아도 중복 자동 제거.

        for(int j : set) {
            System.out.println(j);
        }
    }
}

 

 

성공

통과는 했지만 메모리를 좀 더 적게 사용하는 효율적인 코드로 바꾸고 싶었다. 

1. 중복 제거:
   • 입력 데이터를 배열에 저장한 후, Arrays.sort()로 정렬한다.
   • 정렬된 배열에서 이전 값과 비교해 중복 값을 제거합니다. 추가적인 자료구조(HashSet)를 사용하지 않으므로 메모리 사용량이 줄어든다.
2. 효율적인 출력:
   • StringBuilder를 사용해 출력 성능을 최적화한다. System.out.println() 호출을 반복하지 않아 실행 시간을 줄일 수 있다.
3. HashSet 제거:
   • HashSet은 중복 제거와 함께 삽입 및 조회에 O(1)의 시간복잡도를 제공하지만, 추가적인 메모리를 사용한다. 배열 정렬 후 비교를 통해 중복 제거를 수행하면 더 낮은 메모리 사용량으로 해결 가능하다.

시간 복잡도 분석

• 입력 저장: O(N)
• 정렬: O(N log N)
• 중복 제거 및 출력: O(N)
• 총 시간 복잡도: O(N log N)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class s2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < N; i++) {
            set.add(Integer.parseInt(br.readLine()));
        }

        // HashSet을 List로 변환 후 정렬
        List<Integer> sortedList = new ArrayList<>(set);
        Collections.sort(sortedList);
        
        // 정렬된 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int num : sortedList) {
            sb.append(num).append("\n");
        }

        System.out.println(sb);
    }
}