[백준] 10989 - 수 정렬하기 3 (Golang, Go)

문제의 핵심

주어진 데이터를 오름차순으로 정렬하는 문제이다.

 

해결 방법

int 형 데이터가 10,000,000개 가 주어지기 때문에 자칫하면 메모리초과, 시간초과가 되기 쉽다.

시간복잡도가 O(n) 와 같거나 O(log n) 인 알고리즘을 사용하면 쉽게 풀 수있다.

 

문제가 요구하는 바가 크게 어렵지 않다 생각하여 카운팅 정렬로 해당 문제를 해결하였다.

카운팅 정렬은 O(n+k) 의 시간복잡도를 가지게 된다. n 은 데이터의 갯수이고, k는 데이터의 범위를 나타낸다.
즉 데이터의 범위가 작을수록 높은 성능을 내는 알고리즘이다. 1이5 개가 있다면 1번째 배열에 5를 저장하여

데이터의 갯수를 저장하는 방식의 정렬 알고리즘이다.

 

 

구현 방법 - 소스 코드

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	var n int = 5 //입력받을 수 개수
	var tmp int   //입력 버퍼
	var i int
	var counting [10001]int
	var max = 0
	fmt.Fscanln(reader, &n)

	var cnt int = 0
	for i = 0; i < n; i++ {
		cnt++
		fmt.Fscanf(reader, "%d\n", &tmp) //데이터 입력받기
		counting[tmp]++                  //배열에서 숫자의 갯수를 counting에 저장 (1이 몇개인지 2가 몇개인지)

		if tmp >= max {
			max = tmp
		}
	}

	for i = 0; i <= max; i++ {
		if counting[i] != 0 {
			for j := 0; j < counting[i]; j++ { //couning 배열의 갯수만큼 i를 출력
				fmt.Fprintf(writer, "%d\n", i)
			}
		}
	}
}

counting 배열은 문제에서 제시한 수의 범위가 0 ~ 10000으로, 총 10001개의 배열을 가지게 된다.

데이터를 출력하는데 있어서 모든 배열을 참조하게 되면 성능 저하를 야기할 수 있다.

따라서 데이터를 입력받을 때 최대값을 저장하는 코드를 추가하여 데이터 출력시 최대값이후의 배열을 참조하지 않도록 한다.

 

데이터 입출력시 scanln , println 을 사용하지 않고 Fscanf, Fprintf 를 사용하면 입출력시 성능을 많이 향상시킬 수있다.
정렬문제와 같이 많은 데이터를 입출력할시에는 bufio 패키지의 NewReader NewWriter  메소드를 사용하여
성능을 향상시키자. 성능이 향상되면 프로그램 소요 시간을 단축시킬 수 있다.