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

2751번: 수 정렬하기 2 (acmicpc.net)

2751번: 수 정렬하기 2

 

 

풀이 과정 

 

- 시간 복잡도 O(nlogn)인 힙 정렬을 이용해서 풀이 하였으나 시간 초과 뜸

import java.util.Scanner;

public class Main {
    
    //교환
    static void swap(int[] a, int index1, int index2){
        int t = a[index1];
        a[index1] = a[index2];
        a[index2] = t;
    }
    
    //힙 만들기 
    static void makeHeap(int[] a, int left, int right)
    {
        int temp = a[left]; //루트
        int child; //큰 값을 갖는 자식
        int parent; //부모 
        
        for(parent=left; parent<(right+1)/2; parent=child)
        {
            int cl = parent*2+1;
            int cr = cl+1;
            child=(cr<=right && a[cr]>a[cl])?cr:cl; //큰 쪽을 자식에 대입
            if(temp>=a[child])
                break;
            a[parent]=a[child];
        }
        a[parent] = temp;
    }
    
    //힙 정렬
    static void heapSort(int[] a, int n)
    {
        //a[i]~a[n-1]을 힙으로 만들기
        for(int i=(n-1)/2; i>=0; i--)
        {
            makeHeap(a,i,n-1);
        }
            
        for(int i=n-1; i>0; i--) 
        {
          //가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
          swap(a,0,i); 
          makeHeap(a,0,i-1); //a[0]~a[i-1]을 힙으로 만들기 
         }
      }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        int n[] = new int[num];
        
        for(int i=0; i<num; i++)
        {
            n[i] = sc.nextInt();
        }
        
        heapSort(n,num);
        
        for(int i=0; i<num; i++)
        {
            System.out.println(n[i]);
        }

    }
}

 

 

 

- 구글링 하여  BufferedReader + Collections.sort를 이용한 풀이를 참고해서 품 

참고 블로그 

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바] (tistory.com)

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

 

BufferedReader/BufferedWriter

 

- Buffeer에 있는 IO 클래스 

- 입력된 데이터가 바로 전달되지 않고 중간에 버퍼링이 된 후에 전달

- 출력도 버퍼를 거쳐서 간접적으로 출력장치로 전달되기에 시스템의 데이터처리 효율성을 높여주며 버퍼스트림을 

InputStreamReader / OutPutStreamWriter를 같이 사용하여 버퍼링을 하게 되면 입출력 스트림으로 부터 미리 버퍼에 데이터를 갖다 놓기 때문에 보다 더 효율적인 입출력 가능 

 

 

StringBuilder

 

[JAVA] StringBuilder란? StringBuilder 사용법 (tistory.com)

[JAVA] StringBuilder란? StringBuilder 사용법

 

-  String은 변경 불가능한 문자열을 생성하지만 StringBuilder는 변경 가능한 문자열을 만들어 줌

- StringBuilder의 객체를 생성한 후 , append()의 인자로 연결하고자 하는 문자열을 넣어서 StringBuilder의 객체를 통해 호출 

public class Main
{
    public static void main(String[] args)
    {
        StringBuilder stringBuilder = new StringBuilder();
        ArrayList<String> list = new ArrayList<>();
        list.add("첫 번째, ");
        list.add("두 번째, ");
        list.add("세 번째, ");
        list.add("네 번째, ");
        list.add("다섯 번째");
        for (int i = 0; i < list.size(); i++)
        {
            stringBuilder.append(list.get(i));
        }
        System.out.println(stringBuilder);
    }

}
// >> 첫 번째, 두 번째, 세 번째, 네 번째, 다섯 번째

 

 

 

정답

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
     
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int num = Integer.parseInt(br.readLine());
        
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int i=0; i<num; i++)
        {
            list.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(list);
        
        for(int i : list)
        {
            sb.append(i).append('\n');
        }
        System.out.println(sb);

    }
}