[백준 알고리즘, 단계별로 문제풀기 ] 수 정렬하기3 , 10989번 계수정렬(counting sort)

안녕하세요 호호만두에요

요즈음 다시 백준 알고리즘 문제 풀기를 시작했어요

후 여기 문제들은 쉬운것 같으면서도 어려워요

알고리즘이 답은 맞아도 메모리를 초과하거나 시간이 넘으면

문제가 틀린게 되거든요 ㅠㅠ

 

그래서 다 풀어놓고 느려서

알고리즘을 바꾸고 이러냐고 엄청 오래걸렸어요...

정답률이 낮은 문제들은 괜히 그런게 아니에요

저만 이렇게 문제푸는데 오래걸리는 건지...

코테를 위해 더 열심히 연습해야겠어요

 

그래서 이번에 푼 문제는 백준 10989번 수 정렬하기3 문제에요

계수정렬(counting sort)를 이용하는 문제에요

 

 

문제

---

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

---

 

 

언어는 자바를 이용해서 했어요

코드 자체는 되게 간단해요

N을 입력받고 그 입력받은 N만큼 숫자를 입력받는 방식이에요

입력 받을 때 count_arr에 숫자를 카운팅해서 저장하면 끝이에요

예를들어 1이 두번 나왔다면

count_arr[1] = 2로 되어있어요

 

그리고 1부터 for문을 순회하며 출력해주면 끝!!

코드는 아래와 같고 언어는 JAVA를 이용했어요

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Exam {

	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int input_num = Integer.parseInt(br.readLine());
        
        // index가 해당 숫자, index의 value: index가 나온 횟수
		int [] count_arr = new int[10001];	// 나온 숫자의 개수 count
		int check=0;
		
		//숫자 입력받기
		for(int i=0; i<input_num; i++) {
			int temp = Integer.parseInt(br.readLine());
			count_arr[temp] += 1;	//숫자가 나온 횟수 저장
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for(int i=1; i<= 10000; i++) {
			for(int j=0; j < count_arr[i]; j++) {
				check++;
				bw.write(Integer.toString(i) + "\n");
                //모든 수를 출력했는데 for문 돌고 있을 경우 방지
				if(check == input_num)
					break;
			}
		}
		
		br.close();
		bw.close();
	}

}

 

이를 해결하는데 왜 오래걸렸냐면

시간초과 에러가 났어요

그래서 어떻떻게 하지 고민하다가 해결 방법을 찾았답니다

원래는 Scanner를 이용해서 입력을 받았다가

BufferedReader를 이용하는것으로 바꾸니까 바로 되더라구요

 

찾아보니까 BufferedReader와 Scanner의 버퍼 사이즈가 달라서

데이터의 수가 커지게 되면 성능차이가 엄청 많이나게되요

출처: algospot

이러한 사진을 발견했는데요

Scanner는 6초, BufferedReader는 1초도 안되는

BufferedReader를 사용해야겠죠??

 

<결론>

알고리즘 문제를 풀떄

아니면 왠만하면 Scanner대신 BufferedReader를 사용하자

 

열공!!

댓글과 공감(하트) 부탁드립니다!!