백준 10989번: 수 정렬하기3 [배열][정렬]- Java

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

10989번: 수 정렬하기 3

 

1. 첫 번째 시도 (시간초과)

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어지고 시간 제한은 5초이다.

시간복잡도 O(N^2)인 알고리즘은 시간초과 발생. ( 1초에 1억번 연산 가능하다고 생각할 것 )

N^2는.. 10,000,000*10,000,000이니까  5억이상의 연산이 필요해진다.

 

또한, Scanner와 System.out.println()은 너무나 시간을 많이 잡아먹는 요소기에

BufferdReader와 BufferedWriter를 사용하였다.

package algorithm.boj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Boj10989 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//		StringTokenizer st = new StringTokenizer(br.readLine())
		
		int N = Integer.parseInt(br.readLine());
		Integer arr[] = new Integer[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		//정렬
		for (int i = 1; i < arr.length; i++) {
			int cntBig = 0; //내 앞에 나보다 큰 수가 몇개가 있는지?
			for (int j = i-1; j >= 0; j--) {
				if(arr[i] < arr[j])
					cntBig++;
				else 
					break;
			}
			
			int temp = arr[i];
			for (int j = 0; j < cntBig; j++) {
				arr[i-j] = arr[i-j-1];
			}
			arr[i-cntBig] = temp;
			
		}
		
		//출력
		for (int i = 0; i < arr.length; i++) {
			bw.write(arr[i]+"\n");
		}
		
		bw.flush();
		bw.close();
	}

}

 

 

2. 두번째 시도 - 메모리 초과

와 이건 심지어 메모리가 8MB 제한이였다.

들어오는 값에대한 count 배열을 따로두어서 계산하고 그대로 출력하는 방식을 사용했지만..

arr[], maxVal, cnt[] 등의 변수들의 메모리 공간할당이 8MB를 훌쩍넘김

int숫자 하나당 4byte.. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//		StringTokenizer st = new StringTokenizer(br.readLine())
		
		int N = Integer.parseInt(br.readLine());
		Integer arr[] = new Integer[N];
		
		int maxVal = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			maxVal =Math.max(arr[i], maxVal);
		}
		
		//범위가 적기때문에 cnt 배열 생성
		Integer cnt[] = new Integer[maxVal+1];
		Arrays.fill(cnt, 0);
		for (int i = 0; i < N; i++) {
//			System.out.println(arr[i]);
			cnt[arr[i]]++;
		}
		
		for (int i = 1; i < cnt.length; i++) {
			while(cnt[i] >0) {
				cnt[i]--;
				bw.write(i+"\n");
			}
		}
		
		bw.flush();
		bw.close();
	}
}

 

 

3.세 번째 시도 -성공

불필요한 변수 제거..

 

시간복잡도는 O( max(N,10000))으로 O(N^2)보다 훨씬 단축됨.

들어올 수 있는 자연수가 10,000보다 작거나 같기때문에

cnt배열의 사이즈를 10000으로 하여  무조건 10000번에 대하여 연산이 도는데, 

만일 10000보다 많은 N개의 수(10,000,000까지 가능)가 입력된다면  N만큼 연산이 돌기때문에 

둘중 큰 걸로 복잡도를 도출함

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//		StringTokenizer st = new StringTokenizer(br.readLine())
		
		int N = Integer.parseInt(br.readLine());
//		Integer arr[] = new Integer[N];
		
//		for (int i = 0; i < N; i++) {
//			arr[i] = Integer.parseInt(br.readLine());
//		}
		
		//범위가 적기때문에 cnt 배열 생성
		int cnt[] = new int[10001];
//		Arrays.fill(cnt, 0);
		for (int i = 0; i < N; i++) {
//			System.out.println(arr[i]);
			int num = Integer.parseInt(br.readLine());
			cnt[num]++;
		}
		
		for (int i = 1; i < cnt.length; i++) {
			while(cnt[i] >0) {
				cnt[i]--;
				bw.write(i+"\n");
			}
		}
		
		bw.flush();
		bw.close();
	}
}

 

등급은 브론즈1이지만.. 왜 정답비율이 23%였는지..알거같군..