pullwall
Well done! 코딩
pullwall
전체 방문자
오늘
어제
  • 분류 전체보기 (151)
    • 개발환경 (2)
    • java study (21)
    • 백준 단계별 (51)
    • 알고리즘 (3)
    • AI (43)
    • 클라우드 (3)
      • Kubernetes in Google (3)
    • 논문 (5)
    • 리눅스 (1)
    • AWS (4)
    • 수학 (15)
    • 기타 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 쿠버네티스
  • 논문리뷰
  • 단계별
  • 백준 단계별
  • pytorch
  • LLM
  • 자바
  • Kubernetes
  • dataset
  • 정렬알고리즘
  • 알고리즘
  • Java
  • 수학
  • 백준
  • AWS
  • Ai
  • 자바독학
  • 정렬
  • Google
  • 선택정렬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
pullwall
백준 단계별

[Java] 백준 2751: 수 정렬하기 2

백준 단계별

[Java] 백준 2751: 수 정렬하기 2

2023. 2. 8. 14:29
728x90

일반적인 풀이방법 --> 시간 초과가 발생한다.

아래 더보기를 통해 이유와 코드 확인하기.

더보기

내장 함수를 사용하라고 문제에 나와있지만

Arrays.sort()를 쓰면 시간초과가 발생한다.

 

이유는 Arrays.sort()는 dual-pivot 퀵 정렬을 사용하기 때문이다.

이 알고리즘은 최악의 경우 시간복잡도가 O(n^2)인 알고리즘이기 때문에 시간초과가 발생할 가능성이

높아지는 것이다.

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i=0; i<N ; i++){
            arr[i]=sc.nextInt();
        }
        
        Arrays.sort(arr);

        for(int i=0; i<N ; i++){
            System.out.println(arr[i]);
        }
    }
}

시간 초과를 방지하기 위해 

TimeSort (합병 및 삽입정렬) 알고리즘을 사용하는 Collenctions.sort()를 사용할 것이다.

 

위 알고리즘은 O(n) ~ O(nlogn)의 시간복잡도를 보장하는 강력한 정렬 알고리즘이다.

 

위 함수를 사용할 때 주의할 점은 일반적인 배열을 사용하면 안되고

ArrayList나 LinkedList와 같은 자료구조를 사용해야 동작한다.

 

 

 

Scanner로 그냥 받아서 사용할 때도 시간초과가 나므로

StringBuilder를 이용해서 문제를 해결하였다.

 

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt();
        
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<N ; i++){
            list.add(sc.nextInt());
        }

        Collections.sort(list);

        for(int value : list){
            sb.append(value).append('\n');
        }
        System.out.println(sb);
    }
}
728x90

'백준 단계별' 카테고리의 다른 글

[Java] 백준 2108: 통계학  (0) 2023.02.14
[Java] 백준 10989: 수 정렬하기 3  (0) 2023.02.14
[Java] 백준 25305: 커트라인  (0) 2023.02.02
[Java] 백준 2587: 대표값2  (0) 2023.02.02
[Java] 백준 2750: 수 정렬하기  (0) 2023.02.02
    '백준 단계별' 카테고리의 다른 글
    • [Java] 백준 2108: 통계학
    • [Java] 백준 10989: 수 정렬하기 3
    • [Java] 백준 25305: 커트라인
    • [Java] 백준 2587: 대표값2
    pullwall
    pullwall

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.