[JAVA] 백준 10989번 : 수 정렬하기 3

 

---

 

• 코드

실패 코드 :  시간 초과

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(br.readLine());
			
			for(int j = i - 1; j >= 0; j--) {
				if(array[j] > array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				} else break;
			}
		}
		
		for(int i = 0; i < N; i++)
			System.out.println(array[i]);
	}
}

 

 

실패 코드 : 메모리 초과 append(array[i] + "\n")를 append(array[i]).append("\n")로 바꾸니까 메모리 초과가 안뜨긴 함.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i] + "\n");
		System.out.print(sb);
	}
}

 

성공 코드 : Arrays.sort를 써서 그런지 생각보다 속도가 느리다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i]).append("\n");
		System.out.println(sb);
	}
}

 

성공 코드 : 위의 것에서 array.sort를 쓰지 않고 인덱스에 해당 숫자를 ++해주면서 출력 해주는 코드이다. 위의 코드보다 1/3 정도 더 빠르게 나온다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Algorithm {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
        int[] array = new int[10001];
        
        for (int i = 0; i < N; i++) 
            array[Integer.parseInt(br.readLine())] ++;
         
        for (int i = 1; i <= 10000; i++) {
            if (array[i] > 0) { 
                for (int j = 0; j < array[i]; j++) 
                    sb.append(i).append("\n");                
            }
        }
        System.out.print(sb);
	}
}