[백준] 2751번: 수 정렬하기 2 - JAVA

2024. 9. 20. 01:13·알고리즘

[작성일: 2023. 10. 16]

 

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

 

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            list.add(Integer.valueOf(st.nextToken()));
        }
        Collections.sort(list);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int num : list) {
            bw.write(num + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

 

이 문제는 Arrays.sort로 풀면 시간초과가 뜬다.

처음에는 Scanner랑 sysout이 문제인가? 싶어서 BufferedReader와 BufferedWriter 코드를 바꿔서 풀었지만 그대로 시간초과가 떴다.

 

Arrays.sort는 퀵정렬을 기반으로 하기 때문에 최악의 경우 시간복잡도는 O(n2)가 될 수 있다. 이 문제에서는 n이 1,000,000까지 갈 수 있기 때문에 시간초과가 난 것이다.

 

배열 대신 List를 사용하고 Collections에 있는 sort를 쓰면 되는데, Collections.sort()의 시간복잡도는 O(nlogn)이므로 제한 시간 안에 문제를 수 있다.

 

저작자표시 비영리 변경금지 (새창열림)
'알고리즘' 카테고리의 다른 글
  • [백준] 11650번: 좌표 정렬하기 - JAVA
  • [백준] 10989번: 수 정렬하기 3 - JAVA
  • [백준] 19532번: 수학은 비대면강의입니다 - JAVA
  • [백준] 2231번: 분해합 - JAVA
뚜비
뚜비
1년차 백엔드&iOS 개발자의 감자 탈출 블로그 🥔🥔
  • 뚜비
    뚜비의 개발로그
    뚜비
  • 전체
    오늘
    어제
  • 글쓰기     관리
    • Devlog
      • Back-End
        • Java
        • Spring
        • JPA
        • HTTP
        • Security
        • Back-End
        • Front-End
      • 알고리즘
      • iOS
        • Swift
      • Database
      • Tips
        • Git & GitHub
        • A to Z
      • 프로젝트
      • 생각정리
  • 태그

    다형성
    프로그래머스
    Spring Security
    DB
    Security
    생성자
    Java
    spring
    데이터베이스
    객체
    최주호
    김영한
    변수
    의존성주입
    JPA
    Swift
    Database
    HTTP
    sql
    자바
    백준
    알고리즘
    html
    게시판만들기
    jsp
    성능최적화
    스프링
    javascript
    자바스크립트
    MVC
  • hELLO· Designed By정상우.v4.10.0
뚜비
[백준] 2751번: 수 정렬하기 2 - JAVA
상단으로

티스토리툴바